单源最短路径 给出一个有向图，请输出从某一点出发到所有点的最短路径长度

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来 M 行每行包含三个整数Fi、Gi、Wi，分别表示第 i 条有向边的出发点、目标点和长度。

输出格式：

一行，包含 N 个用空格分隔的整数，其中第 i 个整数表示从点 S 出发到点i的最短路径长度（若 S=i 则最短路径长度为 0，若从点 S 无法到达点 i，则最短路径长度为 2147483647）

输入输出样例

输入样例#1：

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出样例#1：

0 2 4 3

说明

时空限制：

1000ms,128M

数据规模：

对于 20% 的数据：N≤5,M≤15

对于 40% 的数据：N≤100,M≤10000

对于 70% 的数据：N≤1000,M≤100000

对于 100% 的数据：N≤10000,M≤500000

solution

40%的数据，Floyd模板题

70%的数据，dijkstra模板题

100%的数据，spfa/堆优化的dijkstra模板题

code

当然是四种算法都有啦！

#include
#include
#include
#include
using namespace std;
typedef long long ll;

template
void input(T &x) {
    x=0; T a=1;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar())
        if(c=='-') a=-1;
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+c-'0';
    x*=a;
    return;
}

namespace __Floyd {

    const int MAXN=110;
    const int inf=2147483647;

    int dis[MAXN][MAXN];

    void Floyd(int n,int m,int s) {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=inf*(i!=j);
        for(int i=1;i<=m;i++) {
            int u,v,w;
            input(u),input(v),input(w);
            if(w q;
    bool inq[MAXN];
    int dis[MAXN];

    void spfa(int n,int m,int s) {
        for(int i=1;i<=m;i++) {
            int u,v,w;
            input(u),input(v),input(w);
            addedge(u,v,w);
        }
        for(int i=1;i<=n;i++)
            dis[i]=inf,inq[i]=false;
        q.push(s);
        inq[s]=true;
        dis[s]=0;
        while(!q.empty()) {
            int u=q.front();
            q.pop();
            inq[u]=false;
            for(int i=head[u];i;i=edge[i].next) {
                int v=edge[i].v;
                if(dis[u]+edge[i].w (const Data &q)const {
            return dis>q.dis;
        }
    };

    priority_queue,greater > heap;
    int dis[MAXN];
    bool vis[MAXN];

    void dijkstra(int n,int m,int s) {
        for(int i=1;i<=m;i++) {
            int u,v,w;
            input(u),input(v),input(w);
            addedge(u,v,w);
        }
        for(int i=1;i<=n;i++)
            dis[i]=inf,vis[i]=false;
        dis[s]=0;
        heap.push(Data(dis[s],s));
        while(!heap.empty()) {
            Data now=heap.top();
            heap.pop();
            int u=now.x;
            if(vis[u]) continue;
            vis[u]=true;
            for(int i=head[u];i;i=edge[i].next) {
                int v=edge[i].v;
                if(dis[u]+edge[i].w