X19647 - Cheapest Routes

#include <vector>
#include <iostream>
#include <queue>
using namespace std;

typedef pair<int,int> arc;

void route(const vector<int>& hotel, const vector<vector<arc> >& g, int x, int y){
    int n = g.size();
    vector<bool> visited(n,false);
    vector<int> p(n,100001);
    priority_queue <arc,vector<arc>, greater<arc> > PC;
    PC.push(arc(0,x));
    p[x] = 0;
    while(!PC.empty() && !visited[y]){
        arc a = PC.top();
        int u = a.second;
        PC.pop();
        if(!visited[u]){
            visited[u] = true;
            for(int i = 0; i < g[u].size(); ++i){
                arc b = g[u][i];
                int v = b.second;
                int w = b.first;
                if(!visited[v]){
                    if(p[v] > p[u] + w + hotel[v]){
                        p[v] = p[u] + w + hotel[v];
                    }
                    PC.push(arc(p[v],v));
                }
            }
        }
        //cout << u;
    }
    if(p[y] == 100001) cout << "c(" << x << "," << y << ") = +oo" << endl;
    else cout << "c(" << x << "," << y << ") = " << p[y] - hotel[y] << endl;
}

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> hotel(n);
    for(int i = 0; i < n; ++i) cin >> hotel[i];
    vector<vector<arc> > g(n);
    for(int i = 0; i < m; ++i){
        int u,v,w;
        cin >> u >> v >> w;
        g[u].push_back(arc(w,v));
        g[v].push_back(arc(w,u));
    }
    int x,y;
    while(cin >> x >> y){
        if(x == y) cout << "c(" << x << "," << y << ") = 0" << endl;
        else route(hotel,g,x,y);
    }
}