light1002：传送门
【题目大意】
n个点m条边，给一个源点，找出源点到其他点的‘最短路’
定义：找出每条通路中最大的cost，这些最大的cost中找出一个最小的即为‘最短路’，dijkstra变形。dis[i]为s->i的‘最短路’
#include<bits/stdc++.h>
int mp[][],dis[],vis[];
using namespace std;
int n;
void dij(int s)
{
int i,j,k;
for(i=; i<n; i++)
{
dis[i]=mp[s][i];
vis[i]=;
}
vis[s]=;
for(j=; j<n; j++)
{
int min1=1e9;
for(i=; i<n; i++)
{
if(min1>dis[i]&&!vis[i])
{
min1=dis[i];
k=i;
}
}
vis[k]=;
for(i=; i<n; i++)
{
if(!vis[i]&&mp[k][i]<1e9)
{
dis[i]=min(dis[i],max(dis[k],mp[k][i]));
}
}
}
}
int main()
{
int t,u,v,w,i,j;
cin>>t;
for(int co=; co<=t; co++)
{
int m;
scanf("%d%d",&n,&m);
for(i=; i<n; i++)
for(j=; j<n; j++)
{
if(i==j)
mp[i][j]=;
else
mp[i][j]=1e9;
}
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
if(mp[u][v]>w)
mp[u][v]=mp[v][u]=w;
}
int s;
cin>>s;
dij(s);
printf("Case %d:\n",co);
for(i=; i<n; i++)
{
if(dis[i]==1e9)
puts("Impossible");
else
printf("%d\n",dis[i]);
}
}
return ;
}