43 - PD. To The Target.

Sylveon

看大家的CODE，我吐血前趕快發這一篇
原題：http://toj.twbbs.org/oj/pro/43/
AC：http://toj.twbbs.org/oj/chal/2260/ (非管理員不可見)

此題為裸最短路，就是求最短路如此而已。別以為用Warshall可以過，你覺得[tex]10000^3[/tex]可以跑得完再說。
(更正SPFA 原始版本有誤)
多種作法附註解

1.SPFA 32ms

#include<vector>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

struct edge{

    int e,w;

};

vector<edge> V[10000];//Graph Data

int dist[10000]; //Save the distance from S

bool inst[10000];//Flag of if the points have being in stack

int N,M,S,E;

int main(){

    int a,b,w;

    while(~scanf("%d%d",&N,&M)){

        for(int i=0;i<N;++i)V[i].clear();

        memset(dist,0x3f,sizeof(dist)); //init to INF

        memset(inst,false,sizeof(inst));//init to false

        while(M--){

            scanf("%d%d%d",&a,&b,&w);

            V[a].push_back((edge){b,w});//Add edge

            V[b].push_back((edge){a,w});

        }

        scanf("%d%d",&S,&E);

        //Algorithm:SPFA

        dist[S]=0;

        queue<int> st;    //push the S into stack and set dist[S]=0

        st.push(S);        //point : don't set inst[S]=true; it is foolish!

        while(!st.empty()){//loop until stack is empty

            int t=st.front();st.pop();

            inst[t]=false;

            for(edge &e:V[t]){//for C++11

                if(dist[e.e]>dist[t]+e.w){//Relax

                    dist[e.e]=dist[t]+e.w;

                    if(!inst[e.e]){//if point don't stay in stack, push it in

                        st.push(e.e);

                        inst[e.e]=true;

                    }

                }

            }

        }

        printf("%d\n",dist[E]);

    }

}

2.BellmanFord 12ms

#include<vector>

#include<cstdio>

#include<cstring>

#include<queue>

#include<iostream>

using namespace std;

struct edge{

    int s,e,w;

};

vector<edge> e;

int dist[10000]; //Save the distance from S

int N,M,S,E;

int main(){

    int a,b,w;

    while(~scanf("%d%d",&N,&M)){

        memset(dist,0x3f,sizeof(dist)); //init to INF

        while(M--){

            scanf("%d%d%d",&a,&b,&w);

            e.push_back((edge){a,b,w});

            e.push_back((edge){b,a,w});

        }

        scanf("%d%d",&S,&E);

        //Algorithm:Bellman-Ford

        dist[S]=0;

        while(true){

            bool update=false;

            for(edge &t:e){

                if(dist[t.e]>dist[t.s]+t.w){

                    dist[t.e]=dist[t.s]+t.w;

                    update=true;

                }

            }

            if(!update)break;

        }

        printf("%d\n",dist[E]);

    }

}

3.Dijkstra with priority queue 28ms

#include<vector>

#include<cstdio>

#include<cstring>

#include<queue>

#include<iostream>

using namespace std;

struct edge{

    int e,w;

};

inline bool operator<(const edge &a,const edge &b){

    return a.w>b.w; //Notice!

}

vector<edge> V[10000];//Graph Data

int dist[10000]; //Save the distance from S

int N,M,S,E;

int main(){

    int a,b,w;

    while(~scanf("%d%d",&N,&M)){

        for(int i=0;i<N;++i)V[i].clear();

        memset(dist,0x3f,sizeof(dist)); //init to INF

        while(M--){

            scanf("%d%d%d",&a,&b,&w);

            V[a].push_back((edge){b,w});//Add edge

            V[b].push_back((edge){a,w});

        }

        scanf("%d%d",&S,&E);

        //Algorithm:Dijkstra with Priority Queue

        priority_queue<edge> pq;

        pq.push((edge){S,0});

        while(!pq.empty()){

            edge t=pq.top();pq.pop();

            if(t.e==E){

                dist[t.e]=t.w;

                break; //Find answer!

            }

            if(dist[t.e]!=0x3f3f3f3f)continue;

            dist[t.e]=t.w;

            for(edge &e:V[t.e])

                if(dist[e.e]>dist[t.e]+e.w)

                    pq.push((edge){e.e,dist[t.e]+e.w});

        }

        printf("%d\n",dist[E]);

    }

}

allenwhale

這也太善良了吧