Dijkstra 优先级队列 实现 POJ 2387

#include <cstdio>
#include <queue>
#include <list>
#include <utility>

using namespace std;

const int INF = 1000000000;

// <dis and vertex>
typedef pair<int, int> pii;

// <vertex and dis>
typedef pair<int, int> edge;

int T, N;

int d[1001];
bool vis[1001];
list<edge> v[1001];

priority_queue<int, vector<pii>, greater<pii> >q;

void readData()
{
        int f, t, w;
        for(int i = 1; i <= T; i++)
        {
                scanf("%d%d%d", &f, &t, &w);    
                //printf("%d %d %d\n", f, t, w);        
                v[f].push_front(make_pair(t, w));
                v[t].push_front(make_pair(f, w));
        }
}

void init()
{
        for(int i = 1; i < N; i++)
        {
                d[i] = INF;
                vis[i] = false;
        }
        d[N] = 0;

        q.push(make_pair(d[N], N));
}

void dijkstra()
{
        while(!q.empty())
        {
                pii u = q.top();
                q.pop();

                int vertex = u.second;
                if(vis[vertex])
                {
                        continue;
                }

                vis[vertex] = true;
                list<edge> es = v[vertex];
                list<edge>::iterator it;

                //printf("checking %d's edges\n", vertex);
                for(it = es.begin(); it != es.end(); it++)
                {
                        int v = it->first;
                        //printf("checking %d\n", v);
                        if (d[v] > d[vertex] + it->second)
                        {
                                d[v] = d[vertex] + it->second;
                                q.push(make_pair(d[v], v));
                        }
                }
        }
        printf("%d\n", d[1]);
}

int main()
{
        scanf("%d%d", &T, &N);
        readData();
        init();
        dijkstra();
}