C-最短回路(Bellman-FordまたはSPFA)

think:1タイトルは題意で入力データが大きく、頂点数が500000に達していることがわかります.DijkstraアルゴリズムとFloydアルゴリズムで定義された2次元配列では500000*500000には達しないので、Bellma-Fordアルゴリズムを使用することも考えられます.しかし、タグ変数checkを使用して配列disが本ラウンドの緩和中に変化したかどうかをタグする必要があります2重みの有無に注意して図3に重み値が0以上であることを提示し、重み値がゼロ未満であれば、Belloc-FordアルゴリズムまたはBellman-Fordアルゴリズムのキューで最適化するのに適しています4反省しました:自分はtの変化の上で毎回のt++の使用を無視しました.有効データが上書きされ、配列が小さくなったが、自分の感覚計算は1<=n<=50000,1<=m<=20000であるべきであり、今後は注意が必要である5問題の考察点を推測し、重点を把握し、注意細部6さっきSPFAアルゴリズムを学び、SPFAアルゴリズムで実現したが、バックグラウンドデータの比較タイプが似ているため、両アルゴリズムの実現時間の差は多くなく、自分が勉強したばかりなので、いくつかのSPFAアルゴリズムの最適化はまだできないかもしれない.自分は同じようにタグ変数を追加したいと思っているが、結果はタグ変数を追加した後、いくつかの位置が再び緩和されたときに変化が間違っている可能性がある.(Bellman-Fordアルゴリズムのキュー最適化)8 Floydアルゴリズムの時間的複雑度はO(N^3)、Dijkstraアルゴリズムの時間的複雑度はO((M+N)logn)、スタック最適化Dijkstraアルゴリズムの時間的複雑度はO(Mlogn)に達することができ、Bellman-Fordアルゴリズムの時間的複雑度はO(NM)であり、キュー最適化Bellman-Fordアルゴリズムの時間的複雑度は最悪でもO(NM)である9 FloydアルゴリズムとDijkstraアルゴリズムは稠密図に適しており,頂点関係と密接であるが,Bellman‐Fordアルゴリズムはキュー最適化Bellman‐Fordアルゴリズムと疎図に適しており,エッジ関係と密接である.
sdut原題リンク
C–最短時間Time Limit:7000 MS Memory Limit:65536 KB
Problem Descriptionは、n個の点、m個のエッジを含む帯域無方向図を与えます.s,eの最短回路を求めます.最短回路の存在を保証します.
Inputマルチグループ入力.各グループのデータについて.1行目はn,m(1<=n&&n<=5*10^5,1<=m&&m<=2*10^6)を入力する.次にm行、各行の3つの整数、u,v,wは、u,vの間にw(w>=0)の重み値を持つ辺を表す.最後にs,eを入力する.
Outputは、データのセットごとに整数を出力して答えを表します.
Example Input 3 1 1 2 3 1 2
Example Output 3
Hint
Author zmx
以下acceptedコード-Bellman-Ford

#include 
#define INF 0x3f3f3f3f
int dist[500004], u[4000004], v[4000004], w[4000004];
int main()
{
    int n, m, i, k, s, e, check, flag, t, x, y, z;
    while(scanf("%d %d", &n, &m) != EOF)
    {
        t = 1;
        for(i = 1; i <= m; i++)
        {
            scanf("%d %d %d", &x, &y, &z);
            u[t] = x, v[t] = y, w[t] = z;
            t++;
            u[t] = y, v[t] = x, w[t] = z;
            t++;///  ：       +1
        }
        scanf("%d %d", &s, &e);

        for(i = 1; i <= n; i++)
            dist[i] = INF;
        dist[s] = 0;

        m = 2*m;//     

        //Bellman-Ford      
        for(k = 0; k < n-1; k++)
        {
            check = 0;
            for(i = 1; i <= m; i++)
            {
                if(dist[v[i]] > dist[u[i]] + w[i])
                {
                    dist[v[i]] = dist[u[i]] + w[i];
                    check = 1;
                }
            }
            if(check == 0)
                break;
        }

        //      
        flag = 0;
        for(i = 1; i <= m; i++)
        {
            if(dist[v[i]] > dist[u[i]] + w[i])
                flag = 1;
        }
        if(flag)
            printf("error because of -
");
        else
            printf("%d
", dist[e]);
    }
    return 0;
}


/*************************************************** User name: Result: Accepted Take time: 808ms Take Memory: 36672KB Submit time: 2017-02-19 16:33:18 ****************************************************/

以下acceptedコード——SPFAアルゴリズム

#include 
#include 
#define INF 0x3f3f3f3f
int tp, op;
int book[500004], link[500004];
int dist[500004], u[4000004], v[4000004], w[4000004];
int main()
{
    int n, m, i, k, s, e, t, x, y, z;
    while(scanf("%d %d", &n, &m) != EOF)
    {
        tp = op = 0;
        memset(book, -1, sizeof(book));
        memset(link, 0, sizeof(link));

        t = 1;
        for(i = 1; i <= m; i++)
        {
            scanf("%d %d %d", &x, &y, &z);
            u[t] = x, v[t] = y, w[t] = z;
            t++;
            u[t] = y, v[t] = x, w[t] = z;
            t++;
        }
        scanf("%d %d", &s, &e);

        for(i = 1; i <= n; i++)
            dist[i] = INF;
        dist[s] = 0;

        m = 2*m;
        link[tp++] = v[s];
        book[s] = 1;
        while(op < tp)
        {
            op++;
            k = link[op];
            while(k <= m)
            {
                if(dist[v[k]] > dist[u[k]] + w[k])
                {
                    dist[v[k]] = dist[u[k]] + w[k];
                    if(book[k] == 0)
                    {
                        link[tp++] = v[k];
                        book[v[k]] = 1;
                    }
                }
                k++;
            }
        }
        printf("%d
", dist[e]);
    }
    return 0;
}


/***************************************************
User name: 
Result: Accepted
Take time: 860ms
Take Memory: 52840KB
Submit time: 2017-02-19 17:49:05
****************************************************/