【POJ】2387 Til the Cows Come Home

求最短路径的基本题目，直接用Dijkstra算法即可：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 1000 + 10;
const int INF = 999999;

struct Edge{
    
    int to, length;
    Edge(int t, int l): to(t), length(l){
    }
};

struct Point{
    
    int number;
    int distance;
    Point(int n, int d): number(n), distance(d){
    }
    bool operator<(const Point &p) const{
    
        return distance > p.distance;
    }
};
vector<Edge> graph[N];
int dis[N];

void Dijkstra(int s){
    
    priority_queue<Point> pq;
    dis[s] = 0;
    pq.push(Point(s, dis[s]));
    while(!pq.empty()){
    
        int u = pq.top().number;
        pq.pop();
        for(int i = 0; i < graph[u].size(); i ++ ){
    
            int v = graph[u][i].to;
            int l = graph[u][i].length;
            if(dis[v] > dis[u] + l){
    
                dis[v] = dis[u] + l;
                pq.push(Point(v, dis[v]));
            }
        }
    }
}

int main(){
    
    int t, n;
    while(cin >> t >> n){
    
        memset(dis, INF, sizeof(dis));
        while(t -- ){
    
            int from, to, length;
            cin >> from >> to >> length;
            graph[from].push_back(Edge(to, length));
            graph[to].push_back(Edge(from, length));
        }
        Dijkstra(n);
        cout << dis[1] << endl;
    }
    return 0;
}