P3371

题目链接

(因为我太弱了,所以大佬还是不要吐槽了 : ),谢谢)--大佬席------>

算法

我们用一种非常腻害的算法——SPFA

先来一组样例:

（起点为1）

用一个队列维护搜索的依次顺序，再用一个数组维护目前从1号点到i号点的最短长度(权值)，然后命名为vis。当目前不可以到达时，先调整为INF。当输出时判断:当最短距离==INF，输出2147483647。

对了，要记得

vis[1]=0;

然后可以开始搜了!

(目前在队列中的点: 1)

开始搜索点1:

因为从1号点可以到达点2，且从点1到达点2的距离 1+0 小于原本的距离 INF。所以我们更新vis[2]，并把点2加入队列。

同理，调整vis[5]，把点5加入队列。

(目前在队列中的点: 2,5)

开始搜索点2:

因为从2号点可以到达点3，且从点1到达点3的距离 4+1 小于原本的距离 INF。所以我们更新vis[3]，并把点3加入队列。

同理，调整vis[4]，把点4加入队列。

(目前在队列中的点: 5,3,4)

开始搜索点5:

因为从5号点可以到达点3，且从点1到达点3的距离 1+2 小于原本的距离 4。所以我们更新vis[3]，又因为点3已经加入了队列，所以不用重复加入。

(目前在队列中的点: 3,4)

开始搜索点3:

因为从3号点可以到达幻想乡什么也不能到达，所以什么也没有发生QWQ。

(目前在队列中的点: 4)

开始搜索点4:

虽然从4号点可以到达点5，但从点4到达点3的距离 1+4 大于原本的距离 2。所以我们不用更新vis[3]。

(目前在队列中的点:无)

于是输出:

0 1 3 4 2

算法部分完毕！

建图

观察数据规模:

对于100%的数据：N<=10000，M<=500000

QWQ......

考虑使用邻接矩阵...

int a[10010][10010];

点一下有惊喜

QWQ......

好吧，不说了，加入正题：

新的建图方法——链式前向星！！！

已经会了的dalao们就跳过吧QWQ

窝不想讲吗~~~(捂脸)人家不想讲吗

戳一下

(窝还是提供一份链式前向星的代码吧~~~)

int head[maxn];//从i点出发的第一条边
struct egde{
    int to,next_,w;//分别代表每条线目的地,下一条线的下标和权值
}a[maxm]
//这样就可以用下列代码来依次把从now点出发的边遍历
for(i=head[now];i;i=a[i].next_)
//是不是很神奇啊!
//后面的是加入一条边的
void add(int u,int y,int o){
    //建图
    len++;
    c[len].next_=head[u];
    c[len].to=y;
    c[len].dis=o;
    head[u]=len;
}

我再放上代码吧！

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int i,j,k,n,m,s,len;
int vis[10010];
int dis[10010];//判断是否进队
int head[500010];
int dl[500010],l,r;
struct stu{
    int next_,to,w;
}c[500010];
void add(int u,int y,int o){
    //建图
    len++;
    c[len].next_=head[u];
    c[len].to=y;
    c[len].w=o;
    head[u]=len;
}
void SPFA(){
    //初始化
    for(i=1;i<=n;i++){
        vis[i]=INF;
    }
    vis[s]=0;
    l=0;r=1;dl[r]=s;dis[s]=1;
    //设置队列
    while(l^r/*没用的位运算,也就是j!=r*/){
        l++;
        int u=dl[l];
        dis[u]=0;
        for(i=head[u];i;i=c[i].next_){//遍历每条从i点出发的边
            int v=c[i].to;
            if(vis[v]>vis[u]+c[i].w){//如果路径长度小于原长度
                vis[v]=vis[u]+c[i].w;//调整
                if(!dis[v]){
                    //入队
                    dis[v]=1;
                    r++;
                    dl[r]=v;
                }
            }
        }
    }
}
int main(){
    cin>>n>>m>>s;
    //输入
    for(i=1;i<=m;i++){
        int u,y,o;
        scanf("%d%d%d",&u,&y,&o);
        add(u,y,o);
    }
    SPFA();
    //输出
    for(i=1;i<=n;i++)
        if(vis[i]==INF)cout<<2147483647<<" ";
        else cout<<vis[i]<<" ";
    return 0;
}