Uva 10986 Sending email

解題說明：

基本Shortest Path問題：使用Dijstra's Algorithm解

Code：

#include<stdio.h>

#include<stdlib.h>

#include<iostream>

#include<algorithm>

#include<queue>

#include<vector>

#define INF 1000000

using namespace std;

typedef pair<int,int> ii;

vector<ii> edges[50005];

struct Edge

{

    int u,v,dis;

};

int Dijstra(int s,int n,int t)

{

    int dis[20005];

    for(int i=0;i<n;i++) dis[i]=(i==s?0:INF);

    priority_queue<ii,vector<ii>,greater<ii> > pq;

    pq.push(make_pair(0,s));

    while(!pq.empty())

    {

        ii top=pq.top();

        pq.pop();

        int v=top.second,d=top.first;

        if(dis[v]>=d)

        {

            for(int i=0;i<edges[v].size();i++)

            {

                int v2=edges[v][i].first,weight=edges[v][i].second;

                if(dis[v2]>dis[v]+weight)

                {

                    dis[v2]=dis[v]+weight;

                    pq.push(ii(dis[v2],v2));

                }

            }

        }

    }

    return dis[t];

}

int main()

{

    int cas;

    cin>>cas;

    for(int test=1;test<=cas;test++)

    {

        int n,m,s,t;

        cin>>n>>m>>s>>t;

        for(int i=0;i<m;i++)

        {

            int a,b,c;

            cin>>a>>b>>c;

            edges[a].push_back(make_pair(b,c));

            edges[b].push_back(make_pair(a,c));

        }

        int ans=Dijstra(s,n,t);

        printf("Case #%d: ", test);

        if(ans==INF) cout<<"unreachable"<<endl;

        else cout<<ans<<endl;

        for(int i=0;i<n;i++) edges[i].clear();

    }

    return 0;

}