Dij实现最短路

Varuxn · 2019-12-10 18:31:48 · 个人记录

/*
至于SPFA
它已经死了
但，Dij只能处理非负边权的情况
所以
我太难了
——by Varuxn 
*/
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
vector<pair<int,int> > v[10005];//v动态数组存路径 
int n,m,begin,dis[10005];//n表示节点数，m表示路径数，begin表示起始点 ，dis[]存起始点到各点的距离 
bool vis[10005];
priority_queue<pair<int,int> > q;//PQ大根堆辅助运算 
void add_youxiang(int x,int y,int s)
{
    v[x].push_back(make_pair(y,s));//x到y的距离为s； 
}
void add_wuxiang(int x,int y,int s)
{
    v[x].push_back(make_pair(y,s));//x到y的距离为s；
    v[y].push_back(make_pair(x,s));//y到x的距离为s；
}
int main()
{
    n=read();
    m=read();
    begin=read();
    for(int i=1;i<=m;i++)//存图 
    {
        int x,y,s;
        x=read();
        y=read();
        s=read();
        /*有向路*/add_youxiang(x,y,s);
        /*无向路*/add_wuxiang(x,y,s);
    }
    memset(vis,false,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));//初始化起始点到其他各点距离为一个最大值 
    dis[begin]=0;
    q.push(make_pair(0,begin));
    while(!q.empty())
    {
        int s=q.top().second;
        q.pop();//拿出堆顶元素，然后删除 
        if(vis[s]) continue;
        vis[s]=true;
        for(int i=0;i<v[s].size();i++)
            if(dis[v[s][i].first]>dis[s]+v[s][i].second)
            {
                dis[v[s][i].first]=dis[s]+v[s][i].second;//不断更新两点间最小值 
                q.push(make_pair(-dis[v[s][i].first],v[s][i].first));//把下一个点放入小跟堆 
            }
    }
    for(int i=1;i<=n;i++)
    write(dis[i]),cout<<endl;//输出起始点到每个点的最短距离 
    return 0;
}