本文主要是介绍2179: 紧急营救（zzuli），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
2179: 紧急营救
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 120 Solved: 27
Submit Status Web Board
Description
冷锋在非洲完成任务后回到了狼牙特种作战部队。我们知道在战狼二结尾，冷锋正在北极执行任务，而部队发现了龙小云在c国的消息，让冷锋尽快赶往c国。我们知道现在地球上共有n个国家和地区，编号分别为1，2，3...n。国家与国家之间的可能通航班（可能不止一次），也可能没有通航班。共有m次航班，冷锋已经知道了这m次航班的信息(起点 终点，时间)北极的编号是1，c国的编号是n。
而冷峰身为超级英雄一样的的存在，他有一次将航班的时间降为零的能力。
Input
样例数t(t<=10)，接下来又t组样例。 每组样例先输入n , m(n<=1000 , m<=n*(n-1)/2)。
下面m行航班的信息，分别为start , end , time(time <= 100000).表示start和end两地可以互相到达。
Output
对每组样例，输出冷锋到达c国的最短时间，若不能到达输出 "Impossible"。
Sample Input
3
3 1
1 2 1
4 3
1 2 4
2 3 1
2 4 4
3 3
1 2 100000
2 3 1
1 3 2
Sample Output
Impossible
4
0
这个题属于最短路的问题，对于问题中的转化为零这个问题，可以将从起点到各个点的长计算出来，从终点到各个点的最短路径计
出来，然后的dis【u】+dis1【v】就是将u与v之间的路径进行转化为零。
注意：这是个双向边。
注意：要用两次的dj算法。
注意：最后的公式为mix=min（mix，min(dis[u]+dis1[v],dis[v]+dis1[u])）
最下面的代码更简洁。
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1010;
const int inf = 100010;
int n,m;
int vis[maxn],g[maxn][maxn];
int dis[maxn],dis1[maxn];
void dij(){
for(int i=0;i<n;i++){
dis[i]=g[0][i];
}
dis[0]=0;
vis[0]=1;
int temp,flag;
for(int i=0;i<n;i++)
{
temp = inf;
for(int j=0;j<n;j++){
if(!vis[j]&&dis[j]<temp){
temp = dis[j],flag = j;
}
}
if(temp==inf)
break;
vis[flag]=1;
for(int k=0;k<n;k++)
{
if(!vis[k]&&dis[k]>dis[flag]+g[flag][k]){
dis[k]=dis[flag]+g[flag][k];
}
}
}
}
void dik(){
for(int i=0;i<n;i++){
dis1[i]=g[n-1][i];
}
dis1[n-1]=0;
vis[n-1]=1;
int temp,flag;
for(int i=0;i<n;i++)
{
temp = inf;
for(int j=0;j<n;j++){
if(!vis[j]&&dis1[j]<temp){
temp = dis1[j],flag = j;
}
}
if(temp==inf)
break;
vis[flag]=1;
for(int k=0;k<n;k++)
{
if(!vis[k]&&dis1[k]>dis1[flag]+g[flag][k]){
dis1[k]=dis1[flag]+g[flag][k];
}
}
}
}
int main()
{
int mm;
scanf("%d",&mm);
while(mm--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++){
vis[i]=0;
for(int j=0;j<n;j++){
if(i!=j)
g[i][j]=inf;
else
g[i][j]=0;
}
}
int a,b,c;
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
a=a-1;
b=b-1;
if(g[a][b]>c)
g[a][b]=g[b][a]=c;
}
dij();
/* for(int i=0;i<n;i++)
printf("%d ",dis[i]);
printf("\n");*/
for(int i=0;i<n;i++){
vis[i]=0;
}
dik();
/* for(int i=0;i<n;i++)
printf("%d ",dis1[i]);*/
int mix=inf,jiguo;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(g[i][j]!=inf&&i!=j)
{
mix=min(dis[i]+dis1[j],mix);mix=min(dis[j]+dis1[i],mix);//printf("%d\n",mix);
}}
}
// printf("\n%d \n",t);
if(mix>=inf)
printf("Impossible\n");
else
printf("%d\n",mix);
}
}
最后的代码更好，将两个dij合在一起了。#include<bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; int a[1100][1100]; int d1[1100],d2[1100],vis[1100]; int n; void dijstra(int d[],int s) {memset(vis,0,sizeof vis);vis[s]=1;for(int i=1; i<=n; i++)d[i]=a[s][i];for(int i=0; i<n; i++){int mix=inf,t;for(int j=0; j<=n; j++){if(!vis[j]&&mix>d[j]){mix=d[j];t=j;}}if(mix==inf)break;vis[t]=1;for(int j=1; j<=n; j++){if(!vis[j]&&d[j]>d[t]+a[t][j])d[j]=d[t]+a[t][j];}} } int main() {int t;scanf("%d",&t);while(t--){int m;memset(a,0x3f,sizeof a);scanf("%d%d",&n,&m);for(int i=1; i<=n; i++)a[i][i]=0;for(int i=0; i<m; i++){int u,v,w;scanf("%d %d %d",&u,&v,&w);if(a[u][v]>w)a[u][v]=a[v][u]=w;}int mix=inf;dijstra(d1,1),dijstra(d2,n);for(int i=1;i<=n;i++) printf("%d ",d2[i]);for(int i=1; i<=n; i++){for(int j=1; j<=n; j++)if(a[i][j]!=inf&&i!=j){mix=min(d1[i]+d2[j],mix);mix=min(d1[j]+d2[i],mix);}}if(mix==inf)puts("Impossible");elseprintf("%d\n",mix);}return 0; }
这篇关于2179: 紧急营救（zzuli）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
