SPFA模板

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式：

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

输入输出样例

输入样例#1： 4 6 1 1 2 2 2 3 2 2 4 1 1 3 5 3 4 3 1 4 4 输出样例#1： 0 2 4 3

说明

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=15

对于40%的数据：N<=100，M<=10000

对于70%的数据：N<=1000，M<=100000

对于100%的数据：N<=10000，M<=500000

样例说明：

【题解】

vector版本：

#include <cstdio> #include <vector> #include <queue> #include <cstring> #define INF 0x3f3f3f3f using namespace std; const int maxn = 10010, maxm = 500010; int n, Sizem, d[maxn]; struct Edge { int from, to, dist; Edge(int u, int v, int d) : from(u), to(v), dist(d) {} }; vector<int> G[maxn]; vector<Edge> edges; void AddEdge(int from, int to, int dist) { edges.push_back(Edge(from, to, dist)); Sizem = edges.size(); G[from].push_back(Sizem - 1); } bool SPFA(int s) { bool inq[maxn] = {0}; int cnt[maxn] = {0}; queue<int> Q; memset(d, INF, sizeof(d)); d[s] = 0; inq[s] = true; Q.push(s); while (!Q.empty()) { int u = Q.front(); Q.pop(); inq[u] = false; for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; if (!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if (++cnt[e.to] > n) return false; } } } } return true; } int main() { for (int i = 0; i < n; i++) G[i].clear(); edges.clear(); int s, m; scanf("%d%d%d", &n, &m, &s); for (int i = 0; i < m; i++) { int from, to, dist; scanf("%d%d%d", &from, &to, &dist); AddEdge(from - 1, to - 1, dist); } SPFA(s - 1); for (int i = 0; i < n; i++) { if (i) printf(" "); printf("%d", d[i]); } putchar('\n'); return 0; }

链表版：

#include<cstdio> #include<cstring> #include<queue> #define INF 0x3f3f3f3f using namespace std; const int maxm=500010,maxn=10010; struct Edge{ int to,v,next; }edges[maxm]; int Size=0; int head[maxn]={0}; inline void insert(int u,int v,int w){ Size++; edges[Size].to=v; edges[Size].v=w; edges[Size].next=head[u]; head[u]=Size; } int n,m,d[maxn]={0}; bool SPFA(int s){ queue<int>Q; memset(d,INF,sizeof(d)); int cnt[maxn]={0}; bool inq[maxn]={0}; d[s]=0; Q.push(s); while(!Q.empty()){ int u=Q.front();Q.pop(); inq[u]=false; for(int i=head[u];i;i=edges[i].next){ Edge &e=edges[i]; if(d[e.to]>d[u]+e.v){ d[e.to]=d[u]+e.v; if(inq[e.to]==0){ inq[e.to]=true; Q.push(e.to); if(++cnt[e.to]>n)return false; } } } } return true; } int main() { int from,to,dist,s; scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=m;i++){ scanf("%d%d%d",&from,&to,&dist); insert(from,to,dist); } SPFA(s); for(int i=1;i<=n;i++){ if(i!=1)printf(" "); if(d[i]==INF)printf("%d",2147483647); else printf("%d",d[i]); } return 0; }