【題解】POJ 2387 Til the Cows Come Home

【題目敘述】https://vjudge.net/problem/POJ-2387
【解題想法】Dijkstra algorothm 計算最短路徑

  • 起點 N,終點 1。
  • Data input:T 條「雙向」路徑。
  • 接著,用priority_queue (由小到大排序) 實作Dijkstra algorothm,計算最短路徑。
  • dis[i]:除了紀錄從起點走到「頂點-i」的最短距離,也可以用來判斷一個頂點是否已經被拓展過。
  • ⚠️注意:POJ 平台支援的是 C++98,不支援auto自動變數類型。
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

struct cmp{
    bool operator()(pair<int, int> x, pair<int, int> y){
        return x.first > y.first;
    }
};

int n, t, a, b, c, dis[1005];
vector <pair<int, int> > v[1005];
priority_queue <pair<int, int>, vector <pair<int, int> >, cmp> pq;
pair <int, int> now, nxt;

int main() {
    cin >> t >> n;
    for (int i = 0; i < t; i++){
        cin >> a >> b >> c;
        v[a].push_back({c, b});
        v[b].push_back({c, a});
    }
    pq.push({0, n});
    memset(dis, -1, sizeof(dis));
    while (!pq.empty()){
        now = pq.top();
        pq.pop();
        if (dis[now.second] == -1){
            dis[now.second] = now.first;
            for (int i = 0; i < v[now.second].size(); i++){
                nxt = v[now.second][i];
                if (dis[nxt.second] == -1) pq.push({now.first+nxt.first, nxt.second});
            }
        }
    }
    cout << dis[1] << "\n";
}
分享本文 Share with friends