当前位置: 代码迷 >> 综合 >> 【ZZULIOJ 2179:】 紧急营救 【spfa +枚举】
  详细解决方案

【ZZULIOJ 2179:】 紧急营救 【spfa +枚举】

热度:41   发布时间:2023-11-10 04:05:26.0

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).
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

一开始 没想那么多,就想着求出来1-n最短路,然后路径还原,找到其中的最大边,将其减掉就是答案。 然后无限wa.。 最后才发现,可能会有别的1-n的路,虽然不是最短路到达n,但是去掉其的最大边,1-n最短路更小。 然后我就不会写了 TAT 。
然后就看了题解,没想到是枚举边,照着思路写了一发就A了,哎~

看代码吧

#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;const int MAXN = 1e3+10 ;
const int MAXM = 1e6+10;
const int mod  = 1e9+7 ;
const int inf  = 0x3f3f3f3f;struct Edge {int from,to,val,next;
}edge[MAXM];
int head[MAXN],top;
int n,m;
void init(){memset(head,-1,sizeof(head));top=0;
}
void addedge(int a,int b,int c){Edge e={a,b,c,head[a]};edge[top]=e;head[a]=top++;
}void getmap(){while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);addedge(a,b,c);addedge(b,a,c);}
}int dis1[MAXN],dis2[MAXN],vis[MAXN];
void spfa(int st ,int *dis){for(int i=1;i<=n;i++){dis[i]=inf;vis[i]=0;}vis[st]=1;dis[st]=0;queue<int>Q;Q.push(st);while(!Q.empty()){int now=Q.front();Q.pop();vis[now]=0;for(int i=head[now];i!=-1;i=edge[i].next){Edge e=edge[i];if(dis[e.to]>dis[now]+e.val){dis[e.to]=dis[now]+e.val;if(!vis[e.to]) {vis[e.to]=1;Q.push(e.to);}}}}
}
int main(){int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);init();getmap();spfa(1,dis1);spfa(n,dis2);int ans=inf; for(int i=0;i<top;i+=2){
   // 因为不确定 一条边,哪头是正向或者是反向 ,所以要都求一下 。Edge e=edge[i];ans=min(ans,min(dis1[e.from]+dis2[e.to],dis1[e.to]+dis2[e.from]));}if(ans==inf)puts("Impossible");else printf("%d\n",ans);    }return  0;
}