焦翊洋
(༺ཌༀཉིXYD༃ༀད༻)
1
A. [模板]Dijkstra算法
Problem ID: 7511
Contest ID: 3172
必做题
时间限制： 1s
空间限制： 128M
题目描述
给出一个有向图，请输出从 1 号点出发到所有点的最短路径长度。
输入格式
第一行包含两个整数 n,m，分别表示点的个数（1~n编号）、有向边的条数。
接下来 m 行每行包含三个整数 u,v,w，表示有一条 u→v 的，长度为 w 的边。
输出格式
输出一行，共 n 个以空格间隔的整数，第 i 个表示起点到第 i 个点的最短路径，若该点无法到达则输出"inf"。
样例输入
5 6 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4
样例输出
0 2 4 3 inf
数据范围
对于 20% 的数据：1≤n≤5，1≤m≤15；
对于 50% 的数据：1≤n≤1000，1≤m≤105；
对于 100% 的数据：1≤n≤105，1≤m≤5×105，1≤u,v≤n，0≤w<231，保证数据随机生成。
代码 
#include<bits/stdc++.h>
using namespace std;
typedef long long L;
const L INF=0x3f3f3f3f3f3f3f3f;
L n,m,dis[100009],vis[100009],ans,x,y,z;
struct node{L v,w;
bool operator<(const node&t)const{ return w>t.w;}};
vector<node> g[100009];
priority_queue<node> q;
int main(){
scanf("%lld%lld",&n,&m);
for(L i=1;i<=m;i++) scanf("%lld%lld%lld",&x,&y,&z),g[x].push_back({y,z});
memset(dis,INF,sizeof(dis));
dis[1]=0;
q.push(node{1,0});
while(!q.empty()){
node t=q.top();q.pop();
L u=t.v,dist=t.w;
if(vis[u]) continue;
vis[u]=1;
ans+=dist;
for(L i=0;i<g[u].size();i++){
L v=g[u][i].v,w=g[u][i].w;
if(!vis[v]&&dis[v]>w) dis[v]=w,q.push(node{v,dis[v]});
}
}
for(L i=1;i<=n;i++)
if(dis[i]==INF) printf("inf "); else printf("%lld ",dis[i]);
return 0;
}
2 个赞
信友队董老师
(董老师)
2
你这个是用来求最小生成树的，
如果dis[v]（v到生成树的距离） > w（u和v之间的边长）
那么 dis[v]（v到生成树的距离）就等于 w（u和v之间的变成）：因为u是属于生成树的，所以可以这么更新。
而我们要求到起点的最短路
就需要这么去判断，这么去更新
如果dis[v]（v到起点的距离） > dis[u] + w（u到起点的距离+u和v之间的边长）
那么 dis[v]（v到起点的距离） = dis[u] + w（u到起点的距离+u和v之间的边长）：尝试先走到u，再从u到v，这样来更新v到起点的距离
3 个赞
焦翊洋
(༺ཌༀཉིXYD༃ༀད༻)
6
但是样例就输出
0 2 5 4 inf
我真的真的想不出怎么改了
#include<bits/stdc++.h>
using namespace std;
typedef long long L;
const L INF=0x3f3f3f3f3f3f3f3f;
L n,m,dis[100009],vis[100009],ans,x,y,z;
struct node{L v,w;
bool operator<(const node&t)const{ return w>t.w;}};
vector<node> g[100009];
priority_queue<node> q;
int main(){
scanf("%lld%lld",&n,&m);
for(L i=1;i<=m;i++) scanf("%lld%lld%lld",&x,&y,&z),g[x].push_back({y,z});
memset(dis,INF,sizeof(dis));
dis[1]=0;
q.push(node{1,0});
while(!q.empty()){
node t=q.top();q.pop();
L u=t.v,dist=t.w;
if(vis[u]) continue;
vis[u]=1;
ans+=dist;
for(L i=0;i<g[u].size();i++){
L v=g[u][i].v,w=g[u][i].w;
if(dis[v]>dis[u]+w) dis[v]=dis[u]+w;
}
}
for(L i=1;i<=n;i++)
if(dis[i]==INF) printf("inf "); else printf("%lld ",dis[i]);
return 0;
}
3 个赞