簡(jiǎn)單圖論最短路，要用到priority_queue，好久沒(méi)用這個(gè)了，有點(diǎn)生疏。
#include <stdio.h>
#include <string.h>
#include <queue>
#define N 20005
#define M 100005
#define INF 1 << 28
struct node
{
int id, dis;
node (){}
node(int id, int dis): id(id), dis(dis)
{
}
bool operator < (const node &it) const
{
return dis > it.dis;
}
};
struct edge
{
int ed, cost;
edge *next;
}*head[N], table[M];
int pos, dis[N], mk[N];
void Init(int n)
{
pos = 0;
memset(head, 0, sizeof(head));
}
void Add(int a, int b, int c)
{
edge *p = &table[pos++];
p->ed = b; p->cost = c;
p->next = head[a];
head[a] = p;
}
int Dijkstra(int st, int ed, int n)
{
for(int i = 0; i < n; i++)
{
mk[i] = 0;
dis[i] = INF;
}
dis[st] = 0;
std::priority_queue<node> Q;
Q.push(node(st, 0));
node t;
while(!Q.empty())
{
t = Q.top();
Q.pop();
if(mk[t.id]) continue;
if(t.id == ed) return t.dis;
mk[t.id] = 1;
for(edge *p = head[t.id]; p; p = p->next)
{
if(!mk[p->ed] && p->cost + dis[t.id] < dis[p->ed])
{
dis[p->ed] = p->cost + dis[t.id];
Q.push(node(p->ed, dis[p->ed]));
}
}
}
return INF;
}
int main()
{
// freopen("in", "r", stdin);
int cas = 1;
int t, n, m, st, ed;
scanf("%d", &t);
while(t--)
{
scanf("%d %d %d %d", &n, &m, &st, &ed);
Init(n);
for(int i = 0; i < m; i++)
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
Add(a, b, c);
Add(b, a, c);
}
int ans = Dijkstra(st, ed, n);
printf("Case #%d: ", cas++);
if(ans == INF) puts("unreachable");
else printf("%d\n", ans);
}
return 0;
}