Dijkstra

vector<vector<int> > g;
vector<vector<int> > w;
vector<int> d;
vector<int> p;
vector<bool> c;
int n;
const int inf = 2000000000;
typedef pair<int,int> q_e;
void dijkstra(int s)
{
    d.resize(n, inf);
    p.resize(n, -1);
    c.resize(n);
    priority_queue<q_e, vector<q_e>, greater<q_e> > q;
    d[s] = 0;
    q.push(make_pair(0, s));
    while(!q.empty())
    {
        int v = q.top().second;q.pop();
        if(c[v])continue;
        c[v] = true;
        for(int i = 0; i < g[v].size(); i++)
        {
            int tv = g[v][i], tw = w[v][i];
            if(d[v] + tw < d[tv])
            {
                d[tv] = d[v] + tw;
                p[tv] = v;
                q.push(make_pair(d[tv], tv));
            }
        }
    }
}