题目描述
如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。
输入输出格式
输入格式:
第一行包含三个整数N、M、S,分别表示点的个数、有向边的个数、出发点的编号。
接下来M行每行包含三个整数Fi、Gi、Wi,分别表示第i条有向边的出发点、目标点和长度。
输出格式:
一行,包含N个用空格分隔的整数,其中第i个整数表示从点S出发到点i的最短路径长度(若S=i则最短路径长度为0,若从点S无法到达点i,则最短路径长度为2147483647)
输入输出样例
说明
时空限制:1000ms,128M
数据规模:
对于20%的数据:N<=5,M<=15;
对于40%的数据:N<=100,M<=10000;
对于70%的数据:N<=1000,M<=100000;
对于100%的数据:N<=10000,M<=500000。保证数据随机。
对于真正 100% 的数据,请移步 P4779。请注意,该题与本题数据范围略有不同。
样例说明:
图片1到3和1到4的文字位置调换
迪杰斯特拉解法:
#include <bits/stdc++.h> using namespace std; const int INF=2147483647; const int MAXN=1000010; struct qnode { int v; int c; qnode(int v=0,int c=0):v(v),c(c){} bool operator <(const qnode &r)const { return c>r.c; } }; struct Edge { int v,cost; Edge(int v=0,int cost=0):v(v),cost(cost){} }; vector<Edge>E[MAXN];//图 bool vis[MAXN]; int dist[MAXN]; void Dijkstra(int n,int start)//点的编号从1开始 { memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++)dist[i]=INF; priority_queue<qnode>que; while(!que.empty())que.pop();//初始化 dist[start]=0; que.push(qnode(start,0)); qnode tmp; while(!que.empty()) { tmp=que.top(); que.pop(); int u=tmp.v; if(vis[u])continue; vis[u]=true; for(int i=0;i<E[u].size();i++) { int v=E[tmp.v][i].v; int cost=E[u][i].cost; if(!vis[v]&&dist[v]>dist[u]+cost) { dist[v]=dist[u]+cost; que.push(qnode(v,dist[v])); } } } } void addedge(int u,int v,int w) { E[u].push_back(Edge(v,w)); } int main() { int n,m,s; int T; scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n;i++)E[i].clear(); for(int i=0;i<m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); //addedge(v,u,w);无向图 } Dijkstra(n,s); //单源最短路,dist[i]为从源点start到i的最短路 int ans=0; for(int i=1;i<=n;i++) { cout<<dist[i]<<' '; } return 0; }
SPFA解法:
#include<iostream> #include<cstdio> #include<queue> #include<queue> #include<cstring> using namespace std; const int MAXN=1000010; //const int INF=0x3f3f3f3f; const int INF=0x7fffffff; struct edge{ int v,cost; edge(int _v,int _cost):v(_v),cost(_cost){} }; vector<edge>E[MAXN]; void add_edge(int u,int v,int w) { E[u].push_back(edge(v,w)); } bool vis[MAXN]; int cnt[MAXN]; int dist[MAXN]; bool spfa(int start,int n) { memset(vis,false,sizeof(vis)); for(int i=1;i<=n;i++){ dist[i]=INF; } vis[start]=true; dist[start]=0; queue<int>que; while(!que.empty()){ que.pop(); } que.push(start); memset(cnt,0,sizeof(cnt)); cnt[start]=1; while(!que.empty()){ int u=que.front(); que.pop(); vis[u]=false; for(int i=0;i<E[u].size();i++){ int v=E[u][i].v; if(dist[v]>dist[u]+E[u][i].cost){ dist[v]=dist[u]+E[u][i].cost; if(!vis[v]){ vis[v]=true; que.push(v); if(++cnt[v]>n){ return false; } } } } } return true; } int main() { int n,m,s; int T; scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=n;i++)E[i].clear(); for(int i=0;i<m;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add_edge(u,v,w); //addedge(v,u,w);无向图 } spfa(s,n); //单源最短路,dist[i]为从源点start到i的最短路 int ans=0; for(int i=1;i<=n;i++) { cout<<dist[i]<<' '; } return 0; }