uva : 341 - Non-Stop Travel

#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
const int infinity = 1000000000;
struct data {
    int city, dist;
    bool operator < ( const data& p ) const {
        return dist > p.dist;
    }
};

int c[100];

void path(int source, int destination)
{
    if(destination==source)return;
    path(source,c[destination]);
    printf(" %d",destination);
}

int main()
{
   /* freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);*/
    int vertex,i,j,k,l,m,n,y=1;
    while(scanf("%d",&vertex)==1&&vertex!=0)
    {
        vector<int > edge[vertex+1];
        vector<int>cost[vertex+1];
        for(i=1;i<=vertex;i++)
        {
            edge[i].clear();
            cost[i].clear();
            scanf("%d",&n);
            while(n--)
            {
                scanf("%d %d",&l,&m);
                edge[i].push_back(l);
                cost[i].push_back(m);
            }
        }
        int source,destination;
        cin >> source >> destination;
    int d[100];
    for(int i=0; i<100; i++) d[i] = infinity;

    priority_queue<data> q;
    data u, v;
    u.city = source, u.dist = 0;
    q.push( u );
    d[ source ] = 0;

    while( !q.empty() ) {
        u = q.top(); q.pop();
        int ucost = d[ u.city ];

        for(int i=0; i<edge[u.city].size(); i++) {
            v.city = edge[u.city][i], v.dist = cost[u.city][i] + ucost;
            // relaxing :)
            if( d[v.city] > v.dist ) {
                d[v.city] = v.dist;
                q.push( v );
                c[v.city]=u.city;
               // cout << u.city << "   " <<v.city << endl;
            }
        }
    }
    cout << "Case "<<y++ <<": Path = ";
    printf("%d",source);
    path(source, destination);
    printf("; %d second delay\n",d[destination]);
    }
    return 0;
}