interestingLSY 的博客

interestingLSY 的博客

题解 P3371 【【模板】单源最短路径】

posted on 2016-11-18 19:37:28 | under 题解 |

SPFA算法

有一些人说SPFA暴死TLE,但我全AC了呀...

SPFA原理

设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。

代码


#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;
}