图论

衍用指针

可以说是很简单的算法了，加入指针更易理解（口碑不一） 最大感受：

指针大法好

以下提供实现代码

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=10010;
const int INF=0x3fffffff;
int cnt, n, m, x;
int v[maxn], dis[maxn]; 
struct edge{
    int from, to, dis;
    edge * next;
    edge(){
        next=NULL;
    }
    edge(int u, int v, int d, edge * e){
        from=u;
        to=v;
        dis=d;
        next=e;    
    }
};
edge * h[maxn];
void add(int u, int v, int d){
    h[u]=new edge(u, v, d, h[u]);
}
struct mp{
    int pot, dis;
    mp(int x, int y){
        pot=x;
        dis=y;
    }
    bool operator<(mp r)const{
        return dis>r.dis;
    }
};
void dijkstra(int x){
    memset(v, 0, sizeof(v));
    for(int i=1; i<=n; i++)
        dis[i]= i==x ? 0 : INF;
    priority_queue<mp, vector<mp>, less<mp> >    Q;
    Q.push(mp(x, dis[x]));
    while(!Q.empty()){
        int po=Q.top().pot;
        int d=Q.top().dis;
        Q.pop();
        if(v[po])    continue;
        else    v[po]=true;
        for(edge * i=h[po]; i!=NULL; i=i->next){
            int y=i->to;
            if(d+i->dis<=dis[y]){
                dis[y]=d+i->dis;
                Q.push(mp(y, dis[y])); 
            }
        }
    }
}
int main(){
    cin>>n>>m>>x;
    for(int i=1; i<=m; i++){
        int u, v, d;
        cin>>u>>v>>d;
        add(u, v, d);
        add(v, u, d);
    }
    dijkstra(x);
    for(int i=1; i<=n; i++)
        cout<<dis[i]<<endl;
    return 0;
}