SPFA模板

　今天去聽2015ZJOI浙江省隊第二試的集訓，早上就是聽得云里霧里的ORZ，下午某兩集訓隊大神過來將題目，第一個進了IOI的我只聽懂了10%ORZ，第二個人機交互很好玩，找個時間單獨寫下。

? ?順便附帶膜拜各位聚聚，保我明天ZJOI不爆0........

? ?ORZZLD ORZYSY ORZWYH ORZCJH ORZZZQ

好了切入正題——

============================華麗的分割線=====================

今天我們來打打SPFA模板。

去年NOIP我SPFA之前突擊了下然后day2果然我就用spfa坑了T2 60分，簡直了，然而T1寫跪了，其實沒啥區別。然后我就發現SPFA挺重要的，這幾天重新撿起來看看。

先（發）上代碼再說

?

#include<bits/stdc++.h>
using namespace std;
const int MAX=10000;
struct node {
    int to,w,next;
}edge[MAX];
bool used[MAX];
int outqueue[MAX],head[MAX],low[MAX],n,m;
bool spfa(int start) {
    queue<int> q;
    used[start]=1;
    low[start]=0;
    q.push(start);
    while(!q.empty()) {
        int top=q.front();
        q.pop();used[top]=0;
        outqueue[top]++;
        if(outqueue[top]>n) return 0;
        for (int k=head[top];k!=-1;k=edge[k].next)
            if(low[edge[k].to]>low[top]+edge[k].w) {
                low[edge[k].to]=low[top]+edge[k].w;
                if(!used[edge[k].to]) {
                    used[edge[k].to]=1;
                    q.push(edge[k].to);
                }
            }
    }
    return 1;
}
int main() {
    memset(used,0,sizeof(used));
    memset(head,-1,sizeof(head));
    memset(outqueue,0,sizeof(outqueue));
    memset(low,2100000,sizeof(low));
    scanf("%d%d",&n,&m);
    for (int i=1,k=0; i<=m; ++i) {
        int from,to,wei;
        scanf("%d%d%d",&from,&to,&wei);
        edge[k].to=to;
        edge[k].w=wei;
        edge[k].next=head[from];
        head[from]=k++;
    }
    if(spfa(1)) printf("%d\n",low[n]);
    else printf("存在負權環！\n");
    return 0;
}

?

===========================================================

P.S:2015/5/22修改：原來的那份網絡上的模板用完并沒有將used清零，導致了一些小錯誤。

今天在動車（高鐵）上好好理解了下SPFA，弄明白了：

next數組存的是和當前邊一個起點的下/上一條邊。

head[i]存的是以i為起點有多少條邊。

w就不用講了，邊的權值。

SPFA的復雜度為O(kE)，k是常數，所以經常被fzyz的orz神牛們使用。

===========================================================

其實SPFA也不難，就那樣，有點小坑

我是開了個結構體，個人不太喜歡(習慣)寫指針，以前寫指針跪了好多，果然指針沒學好。。。

我都不用指針的，除非萬不得已，然而萬不得已沒有出現過。

——wyh大聚聚

我都喜歡用指針，因為“->”看起來很有美感。。

——cjh大聚聚

好吧話題跑歪了，下面列出可以參考的列表

http://blog.csdn.net/chenjiang492943457/article/details/5375413

http://www.cnblogs.com/devtang/archive/2011/08/25/spfa.html

http://baike.baidu.com/link?url=O0QvxbOY8SVBjrIl6nF6EvMHSslgcEIxfXSoty5SbkA7QjbWZjTWARzwTQsKKbSD5mlASljndZrqYjle_qwcmq

然而我發現SPFA還有優化！！！

LLL和SLF，改天去看看，然后再寫個模板

?

最后聲明下我并不是ZJ的 = =|||