# 【題解】UVa 10986 Sending email

Problem: https://vjudge.net/problem/UVA-10986

Solution: Calculate the shortest path using Dijkstra algorithm

#### 【做法1】priority_queue

• vector G[maxn]: 存圖 (adjacency list)
• dist[maxn]: 紀錄起點到每一點的最短距離，初始設為INF，起點設成 0。
• priority_queue<P, vector<P>, greater<P> > pq: 記錄尚未拓展的頂點，指定greater<P>來依照first由小到大排序。first 是最短距離，second是頂點編號。
• Line-38：dist[p.S] < p.F 表示頂點 v 已經被拓展過了。
```#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
#define pii pair<int, int>
#define P pair<long long, int>
#define F first
#define S second
#define INF 0x3F3F3F3F3F3F3F3F
const int maxn = 20000;

vector<pii> G[maxn];
long long dist[maxn];

int main() {
int N, n, m, S, T;
int u, v, w;
cin >> N;
for (int Case=1; Case<=N; Case++){
for (int i=0; i<maxn; i++) G[i].clear();
cin >> n >> m >> S >> T;
for (int i=0; i<m; i++){
cin >> u >> v >> w;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
// Dijkstra - priority_queue
memset(dist, 0x3F, sizeof(dist));
priority_queue<P, vector<P>, greater<P> > pq;
dist[S] = 0;
pq.push({0, S});
while (!pq.empty()){
P p = pq.top();
pq.pop();
if (dist[p.S] < p.F) continue;
for (auto nxt: G[p.S]){
if (dist[nxt.F] > dist[p.S] + nxt.S){
dist[nxt.F] = dist[p.S] + nxt.S;
pq.push({dist[nxt.F], nxt.F});
}
}
}
cout << "Case #" << Case << ": ";
if (dist[T] == INF) cout << "unreachable\n";
else cout << dist[T] << '\n';
}
return 0;
}
```

#### 【做法2】set

• vector G[maxn]: 存圖 (adjacency list)
• dist[maxn]: 紀錄起點到每一點的最短距離，初始設為INF，起點設成 0。
• set<P> st: 記錄尚未拓展的頂點，依照first由小到大排序。first 是最短距離，second是頂點編號。
• Line-41：N不是很大時，可略。
```#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <utility>
using namespace std;
#define pii pair<int, int>
#define P pair<long long, int>
#define F first
#define S second
#define INF 0x3F3F3F3F3F3F3F3F
const int maxn = 20000;

vector<pii> G[maxn];
long long dist[maxn];

int main() {
int N, n, m, S, T;
int u, v, w;
cin >> N;
for (int Case=1; Case<=N; Case++){
for (int i=0; i<maxn; i++) G[i].clear();
cin >> n >> m >> S >> T;
for (int i=0; i<m; i++){
cin >> u >> v >> w;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
// Dijkstra - set
memset(dist, 0x3F, sizeof(dist));
set<P> st;
dist[S] = 0;
st.insert({0, S});
while (!st.empty()){
P p = *st.begin();
st.erase(p);
if (dist[p.S] < p.F) continue;
for (auto nxt : G[p.S]){
long long new_dist = p.F + nxt.S;
if (new_dist < dist[nxt.F]){
//st.erase({dist[nxt.F], nxt.F});
dist[nxt.F] = new_dist;
st.insert({dist[nxt.F], nxt.F});
}
}
}
cout << "Case #" << Case << ": ";
if (dist[T] == INF) cout << "unreachable\n";
else cout << dist[T] << '\n';
}
return 0;
}
```