题解 P3371 【【模板】单源最短路径】
interestingLSY
2016-11-18 19:37:28
#SPFA算法
##有一些人说SPFA暴死TLE，但我全AC了呀...
#SPFA原理
设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
#代码
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <vector>
#include <string.h>
using namespace std;
#define uint unsigned int
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pb push\_back
#define mp make\_pair
#define INF 2147483647
#define LINF 9999999999
#define ms(l) memset(l,0,sizeof(l))
uint n,m,spoint;
uint dis[10001];
class Edge{
public:
uint to,cost;
};
vector<Edge> data[10000];
void addedge(uint fr,uint to,uint co){
Edge e1;
e1.to = to; e1.cost = co;
data[fr].pb(e1);
}
void spfa(void){
queue<uint> q; bool at[10001];
q.push(spoint); ms(at);
for(uint i = 1;i <= n;i++)
dis[i] = INF;
dis[spoint] = 0; at[spoint] = 1;
while(!q.empty()){
uint u;
u = q.front();
q.pop(); at[u] = 0;
for(uint i = 0;i < data[u].size();i++)
if(dis[u]+data[u][i].cost < dis[data[u][i].to]){
dis[data[u][i].to] = dis[u]+data[u][i].cost;
if(!at[data[u][i].to]){
at[data[u][i].to] = 1;
q.push(data[u][i].to);
}
}
}
}
int main(){
//freopen("i.txt","r",stdin);
cin >> n >> m >> spoint;
for(uint i = 1;i <= m;i++){
uint f,t,c;
cin >> f >> t >> c;
addedge(f,t,c);
}
spfa();
for(uint i = 1;i <= n;i++)
cout << dis[i] << ' ';
cout << endl;
return 0;
}