spfa

Ykimna · 2018-08-08 13:22:52 · 题解

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int N = 1e4 + 100;
struct Node
{
    int ed,w;//ed为目标点,w为距离;
};
vector<struct Node> vt[N];
int n,m,s;
bool vis[N];
int dist[N];
const int INF = 0x3f3f3f3f;

void spfa()//个人感脚和bfs差不多 
{
    memset(vis,false,sizeof(vis));
    memset(dist,INF,sizeof(dist));//初始化 
    queue<int> que;
    que.push(s);
    dist[s]=0;
    vis[s]=true;//初始起点 
    while(!que.empty())
    {
        int x=que.front();
        que.pop();
        vis[x]=false;//
        for(int i=0;i<vt[x].size();i++)
        {
            int y=vt[x][i].ed;
            int z=vt[x][i].w;
            if(dist[y]>dist[x]+z)
            {
                dist[y]=dist[x]+z;
                if(!vis[y]) que.push(y),vis[y]=true;
            }
        }
    }
}

int main()
{
    cin>>n>>m>>s;//点的数量，边的数量，出发的点
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;//出发点，目标点，距离；
        struct Node now;
        now.ed=y;now.w=z;
        vt[x].push_back(now);//vector的下标为出发点
    }
    //dijstra();//两种方法自己选择 
    spfa();
    for(int i=1;i<=n;i++)
    {
        if(dist[i]==INF)
        {
            dist[i]=2147483647;
        } 
        cout<<dist[i]<<" ";
    }
    return 0;
}