【題目敘述】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";
}
}