蓝桥杯 算法训练 最短路
给定一个n个顶点,m条边的有向图(其中某些边权可能为负,但保证没有负环)。请你计算从1号点到其他点的最短路(顶点从1到n编号)。
第一行两个整数n, m。
接下来的m行,每行有三个整数u, v, l,表示u到v有一条长度为l的边。
1 2 -1
2 3 -1
3 1 2
-2
对于10%的数据,n = 2,m = 2。
对于30%的数据,n <= 5,m <= 10。
对于100%的数据,1 <= n <= 20000,1 <= m <= 200000,-10000 <= l <= 10000,保证从任意顶点都能到达其他所有顶点。
#include<stdio.h> #include<string.h> #include<queue> #include<algorithm> #include<iostream> #include<math.h> using namespace std; #define N 200000+5 const int inf=0x3f3f3f3f; struct node { int u,v,next,w; }e[N]; int head[N]; int dis[N],vis[N]; int n,m,cnt; void add(int u,int v,int w) { e[cnt].u=u; e[cnt].v=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt++; } void spfa() { int i,u,v,w; queue<int>q; for(i=1;i<=n;i++) { dis[i]=inf; vis[i]=0; } dis[1]=0; vis[1]=1; q.push(1); while(!q.empty()) { u=q.front(); q.pop(); vis[u]=0; for(i=head[u];i!=-1;i=e[i].next) { v=e[i].v; w=e[i].w; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; if(!vis[v]) { vis[v]=1; q.push(v); } } } } } int main() { int i,u,v,w; while(~scanf("%d%d",&n,&m)) { cnt=0; memset(head,-1,sizeof(head)); for(i=0;i<m;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); } spfa(); for(i=2;i<=n;i++) printf("%d\n",dis[i]); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。