C++课后习题训练记录Day144

1.练习项目 ：

问题描述

小明是蓝桥王国的王子，今天是他登基之日。

在即将成为国王之前，老国王给他出了道题，他想要考验小明是否有能力管理国家。

题目的内容如下：

蓝桥王国一共有 N 个建筑和 M 条单向道路，每条道路都连接着两个建筑，每个建筑都有自己编号，分别为 1∼N 。（其中皇宫的编号为 1）

国王想让小明回答从皇宫到每个建筑的最短路径是多少，但紧张的小明此时已经无法思考，请你编写程序帮助小明回答国王的考核。

输入描述

输入第一行包含两个正整数 N,M。

第 2 到 M+1 行每行包含三个正整数 u,v,w，表示 u→v 之间存在一条距离为 w 的路。

1≤N≤3×105，1≤m≤106，1≤ui,vi≤N，0≤wi≤109。

输出描述

输出仅一行，共 N 个数，分别表示从皇宫到编号为 1∼N 建筑的最短距离，两两之间用空格隔开。（如果无法到达则输出 −1）

2.选择课程

在蓝桥云课中选择题库，选择题号1122并开始练习。

3.开始练习

（1）源码 ：

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const ll N = 3e5+10;

const ll inf = 2e18;

struct Node{

ll x,w;

bool operator < (const Node &u)const{

return w==u.w?x<u.x:w>u.w;

}

};

vector<Node>g[N];

ll d[N];

int n,m;

void dijstra(int st)

{

for(int i=1;i<=n;i++)d[i]=inf;

bitset<N>vis;

priority_queue<Node>pq;

pq.push({st,d[st]=0});

while(pq.size()){

int x=pq.top().x;

int w=pq.top().w;

pq.pop();

if(vis[x])continue;

vis[x]=true;

//拓展

for(const auto &[y,dw]:g[x]){

if(d[x]+dw<d[y]){

d[y]=d[x]+dw;

pq.push({y,d[y]});

}

}

}

}

int main()

{

ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

cin>>n>>m;

while(m--){

int x,y,w;cin>>x>>y>>w;

g[x].push_back({y,w});

}

dijstra(1);

for(int i=1;i<=n;i++){

cout<<(d[i]>=inf?-1:d[i])<<' ';

}

return 0;

}

（2）检验结果

对此代码进行检验，检验后无报错，提交此代码，判题结果为正确100分。

（3）练习心得：注意每段代码末尾的分号是否存在 ，如不存在则需即使补充；输入法 是否切换 为英语模式；语法是否错误。