【題解】GreenJudge g053: B.水之國奇幻冒險

【題目敘述】http://tcgs.tc.edu.tw:1218/ShowProblem?problemid=g053
【解題想法】Dijkstra algorithm 計算最短路徑

#include <iostream>  
#include <vector>  
#include <set>  
using namespace std;  
  
vector <pair<int, int> > v[105];  
set <pair<int, int> > st;  
int exp[105], dis[105];  
pair<int, int>p;  
  
int main() {  
    int num, stops, roads, b, c, d;  
    cin >> num;  
    while (num--){  
        cin >> stops >> roads;  
        for (int i = 0; i < stops; i++){  
            exp[i] = 0;  
            dis[i] = 300;  
            v[i].clear();  
        }  
        st.clear();  
        dis[0] = 0;  
        for (int i = 0; i < roads; i++){  
            cin >> b >> c >> d;  
            b--;  
            c--;  
            p.first = d;  
            p.second = c;  
            v[b].push_back(p);  
            p.second = b;  
            v[ c].push_back(p);  
        }  
        p.first = 0;  
        p.second = 0;  
        st.insert(p);  
        pair <int, int> now;  
        while(!st.empty()){  
            now = *st.begin();  
            st.erase(now);  
            if (exp[now.second] == 1) continue;  
            exp[now.second] = 1;  
            for (int i = 0; i < v[now.second].size(); i++){  
                p = v[now.second][i];  
                p.first = max(now.first, p.first);  
                st.insert(p);  
                dis[p.second] = min(dis[p.second], p.first);  
            }  
        }  
        cout << dis[stops-1] << "\n";  
    }  
}  
分享本文 Share with friends