点击打开链接
题目描述
世界上最遥远的距离不是生与死,而是我站在你面前,你却不知道我爱你。
相传，每一对男女相恋之前都生活在不同的孤岛上，如果一个人向另一个发出追求，爱神就会在TA们之间架构起道路。当然，不经历考验的恋爱是脆弱的，所以爱神的道路会通过许多其他孤岛间接相连。
为了加大难度，爱神架构起了多条可能的道路，而通过不同的道路会消耗不同的爱意值，如果花费的爱意值过多，就会导致爱情失去魅力。所以每个人都希望自己能选择一条花费最小的道路。
幸运的是，如果被追求者对追求者也有好感，那么TA会提前告知追求者通过每条道路需要花费的爱意值。然而，没有事情是完美的，即使两人相爱，爱神也有可能不给TA们机会，因为有可能爱神给的道路无法使两人连通。
作为一名幸运儿，你现在追求的那个人已经告诉了你每条道路的信息，你能否求出需要花费的最少爱意值呢？又或者……到达彼岸根本是个无法完成的任务。
假设你现在处于孤岛1，你爱的人处于孤岛n。
输入
第一行是一个整数T，代表T组测试数据。
每组测试数据包含n个点，m条路，接下来m行，每行包含三个数a、b、c，其中c表示a，b两个孤岛间的这条路上你需要花费的爱意值。
T,n<10
输出
每组测试结果前请先输出：“Case #: ”，#代表第几组测试（从1开始）。
如果你能够到达爱人处，输出最少花费爱意值，否则，请输出“Impossible”。
样例输入
2
3 2
1 2 50
2 3 10
3 1
1 2 40
样例输出
Case 1: 60
Case 2: Impossible 题意：关于0x3f3f3f3f的使用可参考：
0x3f3f3f3f3f.
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int f1=0x3f3f3f3f;
const int ma=1e4+9;
struct tt
{
int a,b;
};
vector <tt > vec[ma];
int d[ma];
int spfa(int s,int q)
{
queue<int >que;
que.push(s);
memset(d,0x3f,sizeof(d));
d[s]=0;
while(!que.empty())
{
int v=que.front();que.pop();
for(int j=0;j<vec[v].size();j++)
{
tt &q=vec[v][j];
if(d[v]+q.b<d[q.a])
{
d[q.a]=d[v]+q.b;
que.push(q.a);
}
}
}
return d[q];
}
int main()
{
int i,k=0;
scanf("%d",&i);
while(i--)
{
int n,m;k++;
scanf("%d%d",&n,&m);
for(int j=0;j<m;j++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
vec[x].push_back({y,z});
vec[y].push_back({x,z});
}
int ans=spfa(1,n);
if(ans==f1)
{
printf("Case %d: Impossible\n",k);
}
else
{
printf("Case %d: %d\n",k,ans);
}
for(int j=0;j<=n;j++)
{
vec[j].clear();
}
}
return 0;
}
