10986 - Sending email( UVA SOLUTION )

#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
#define MAX 100000
int N,n,m,S,T,u,v,w;
#define INF 1e9
pair<int , int > pii;
vector < pair<int , int >  > G[MAX];
priority_queue < pair<int , int > , vector < pair<int , int > >,greater<pair<int ,int> > > pq;
int d[MAX];

bool change;

void dijkstra (int src)
{
    pii.first=0;
    pii.second=src;
    pq.push(pii);
    d[src]=0;
    change = false;
    int i;
    while(!pq.empty())
    {
        u=pq.top().second;
        w=pq.top().first;
        pq.pop();

        for( i=0;i<G[u].size();i++)
        {
            v=G[u][i].first;
            w=G[u][i].second;
            if(d[v]>d[u]+w)
            {
                if(v==T) change =true;

                d[v]=d[u]+w;

                pii.first=d[v];
                pii.second=v;
                pq.push(pii);
            }

        }
    }
}



int main()
{
    cin >> N;
    int i;
    for(i=1;i<=N;i++)
    {
        cin>>n>>m>>S>>T;

        for(int j=0;j<m;j++)
        {
            cin>>u>>v>>w;
            pii.first=v;
            pii.second=w;
            G[u].push_back(pii);
            pii.first=u;
            pii.second=w;
            G[v].push_back(pii);

        }
        for(int yy=0;yy<MAX;yy++)
            d[yy]=INF;

        dijkstra( S);
        printf("Case #%d: ",i);
        if(change)
            cout<<d[T]<<endl;
        else
            cout<<"unreachable"<<endl;
        for(int kk=0;kk<MAX;kk++)
            G[kk].clear();


    }


    return 0;
}

SHARE

Amit Ghosh

• 
• 
• 
• 
•