ford 超时 使用优先队列的Dijkstra 算法
//#include <cstdio>
//#include <cstring>
//#include <algorithm>
//#define INF 500000000
//using namespace std;
//int a[20010][20010];
//int main()
//{
// int t, ca = 1;
// scanf("%d",&t);
// while(t--)
// {
// int n,m,s,v;
// scanf("%d%d%d%d",&n,&m,&s,&v);
// for(int i = 0; i <= n; i++)
// for(int j = 0; j <= n; j++)
// {
// if(i == j)
// a[i][j] = 0;
// else
// a[i][j] = INF;
// }
// for(int i = 0; i < m; i++)
// {
// int x,y,w;
// scanf("%d%d%d",&x,&y,&w);
// a[x][y] = a[y][x] = w;
// }
// for(int k = 0; k < n; k++)
// for(int i = 0; i < n; i++)
// for(int j = 0; j < n; j++)
// {
// a[i][j] = min(a[i][j], a[i][k]+a[k][j]);
// }
// if(a[s][v] < INF)
// printf("Case #%d: %d\n",ca++,a[s][v]);
// else
// printf("Case #%d: unreachable\n",ca++);
// }
// return 0;
//}
#include <cstdio>
#include <cstring>
#include <queue> #define N 20005
#define M 100005
#define INF 1<<28 struct node
{
int id, dd;
node(int i, int j)
{
id = i;
dd = j;
}
bool operator < (const node &it) const
{
return dd > it.dd;
}
}; int first[M],v[M],w[M],next[M],dis[N],vis[N]; int Dijkstra(int st, int ed, int n)
{
for(int i = 0; i < n; i++)
{
vis[i] = 0;
dis[i] = INF;
}
dis[st] = 0;
std::priority_queue<node> Q;
Q.push(node(st, 0));
while(!Q.empty())
{
node t = Q.top();
Q.pop();
if(vis[t.id]) continue;
if(t.id == ed)
return t.dd;
vis[t.id] = 1;
for(int e = first[t.id]; e != -1; e = next[e])
{
if(dis[v[e]] > dis[t.id] + w[e])
{
dis[v[e]] = dis[t.id] + w[e];
Q.push(node(v[e], dis[v[e]]));
}
}
}
return INF;
} int main()
{
int ca = 1;
int t;
scanf("%d", &t);
while(t--)
{
int n,m,s,d;
scanf("%d%d%d%d", &n, &m, &s, &d);
memset(first, -1, sizeof(first));
int l = 0;
for(int i = 0; i < m; i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
next[l] = first[a];
v[l] = b;
w[l] = c;
first[a] = l++;
next[l]=first[b];
v[l] = a;
w[l] = c;
first[b] = l++;
}
int ans = Dijkstra(s, d, n);
printf("Case #%d: ", ca++);
if(ans == INF)
puts("unreachable");
else
printf("%d\n", ans);
}
return 0;
}