單源最短路（SPFA模闆）--------------#1093 : 最短路徑·三：SPFA算法

問題描述

給定一個n個頂點，m條邊的有向圖（其中某些邊權可能為負，但保證沒有負環）。請你計算從1号點到其他點的最短路（頂點從1到n編号）。

輸入格式

第一行兩個整數n, m。

接下來的m行，每行有三個整數u, v, l，表示u到v有一條長度為l的邊。

輸出格式

共n-1行，第i行表示1号點到i+1号點的最短路。

樣例輸入

3 3

1 2 -1

2 3 -1

3 1 2

樣例輸出

-1

-2

資料規模與約定

對于10%的資料，n = 2，m = 2。

對于30%的資料，n <= 5，m <= 10。

對于100%的資料，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保證從任意頂點都能到達其他所有頂點。

思路：SPFA模闆即可。試了一發Floyd，TLE...

代碼（SPFA）：

///SPFA算法
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
struct Edge
{
    int u,v,l;
    int next;
}e[200000<<2];

int head[200010];   ///鄰接表建立
int dis[200010];   ///s到各點的距離
int vis[200010];  ///是否通路過
int cnt[200010];  ///進隊次數

void AddEdge(int u,int v,int l,int i)
{
    e[i].u=u;
    e[i].v=v;
    e[i].l=l;
    e[i].next = head[u];
    head[u]=i;
}

int relax(int u,int v,int c)  ///路徑松弛
{
    if(dis[v]>dis[u]+c)
    {
        dis[v]=dis[u]+c;
        return 1;
    }
    return 0;
}

void SPFA(int s)
{
    memset(cnt,0,sizeof(cnt));
    dis[s]=0;
    queue<int>Q;
    Q.push(s);
    vis[s]=1;
    cnt[s]++;
    while(!Q.empty())
    {
        int u,v;
        u=Q.front();
        Q.pop();
        vis[u]=0;
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            v=e[i].v;
            if(relax(u,v,e[i].l)==1&&!vis[v])
            {
                Q.push(v);
                vis[v]=1;
            }
        }
    }
}
int main()
{
    int n,m;
    int u,v,l;
    cin>>n>>m;
    memset(e,-1,sizeof(e));
    for(int i=1;i<=n;i++)
    {
        head[i]=-1;
        vis[i]=0;
        dis[i]=inf;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>l;
        AddEdge(u,v,l,i);
    }
    SPFA(1);
    for(int i=2;i<=n;i++)
    {
        cout<<dis[i]<<endl;
    }
    return 0;
}
           

Floyd算法代碼（逾時）：

///floyd算法
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int a[8010][8010];
int main()
{
    int n,m;
    int u,v,l;
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) a[i][j]=0;
            else a[i][j]=inf;
        }
    }

    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>l;
        a[u][v]=min(a[u][v],l);
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        cout<<a[1][i]<<endl;
    }
    return 0;
}
           

-------------------------------------------------------------------------------------------

#1093 : 最短路徑·三：SPFA算法

時間限制:10000ms

單點時限:1000ms

記憶體限制:256MB

描述

萬聖節的晚上，小Hi和小Ho在吃過晚飯之後，來到了一個巨大的鬼屋！

鬼屋中一共有N個地點，分别編号為1..N，這N個地點之間互相有一些道路連通，兩個地點之間可能有多條道路連通，但是并不存在一條兩端都是同一個地點的道路。

不過這個鬼屋雖然很大，但是其中的道路并不算多，是以小Hi還是希望能夠知道從入口到出口的最短距離是多少？

提示：Super Programming Festival Algorithm。

輸入

每個測試點（輸入檔案）有且僅有一組測試資料。

在一組測試資料中：

第1行為4個整數N、M、S、T，分别表示鬼屋中地點的個數和道路的條數，入口（也是一個地點）的編号，出口（同樣也是一個地點）的編号。

接下來的M行，每行描述一條道路：其中的第i行為三個整數u_i, v_i, length_i，表明在編号為u_i的地點和編号為v_i的地點之間有一條長度為length_i的道路。

對于100%的資料，滿足N<=10^5，M<=10^6, 1 <= length_i <= 10^3, 1 <= S, T <= N, 且S不等于T。

對于100%的資料，滿足小Hi和小Ho總是有辦法從入口通過地圖上标注出來的道路到達出口。

輸出

對于每組測試資料，輸出一個整數Ans，表示那麼小Hi和小Ho為了走出鬼屋至少要走的路程。

樣例輸入

5 10 3 5
1 2 997
2 3 505
3 4 118
4 5 54
3 5 480
3 4 796
5 2 794
2 5 146
5 4 604
2 5 63
      

樣例輸出

172
思路：      

SPFA模闆即可，注意路徑要有正反。

代碼：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define inf 0x3f3f3f3f

struct Node{
    int u,v,w;
    int next;
}node[1000000*4];

int head[1000000*4];
int dis[1000000*4];
int vis[1000000*4];
int n,m;
int num;

void AddEdge(int u,int v,int w)
{

    node[num].u=u;
    node[num].v=v;
    node[num].w=w;
    node[num].next=head[u];
    head[u]=num++;
}

bool relax(int u,int v,int t)
{
    if(dis[v]>dis[u]+t)
    {
        dis[v]=dis[u]+t;
        return true;
    }
    return false;
}
void SPFA(int s)
{
    dis[s]=0;
    vis[s]=1;
    queue<int> Q;
    Q.push(s);
    while(!Q.empty())
    {
        int u,v;
        u=Q.front();
        Q.pop();
        vis[u]=0;
        for(int i=head[u];i!=-1;i=node[i].next)
        {
            v=node[i].v;
            if(relax(u,v,node[i].w)&&!vis[v])
            {
                Q.push(v);
                vis[v]=1;
            }
        }
    }
}
int main()
{
    int start,endd;
    int u,v,w;
    memset(node,-1,sizeof(node));
    cin>>n>>m>>start>>endd;
    for(int i=1;i<=n;i++)
    {
        head[i]=-1;
        dis[i]=inf;
        vis[i]=0;
    }
    num=1;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        AddEdge(u,v,w);
        AddEdge(v,u,w);
    }
    SPFA(start);
    cout<<dis[endd]<<endl;
    return 0;
}