枚举最短路径+SPFA
2024-10-19 05:10:06
Description
The final battle is coming. Now Harry Potter is located at city 1, and Voldemort is located at city n. To make the world peace as soon as possible, Of course, Harry Potter will choose the shortest road between city 1 and city n. But unfortunately, Voldemort is so powerful that he can choose to destroy any one of the existing roads as he wish, but he can only destroy one. Now given the roads between cities, you are to give the shortest time that Harry Potter can reach city n and begin the battle in the worst case.
Input
First line, case number t (t<=20).
Then for each case: an integer n (2<=n<=1000) means the number of city in the magical world, the cities are numbered from 1 to n. Then an integer m means the roads in the magical world, m (0< m <=50000). Following m lines, each line with three integer u, v, w (u != v,1 <=u, v<=n, 1<=w <1000), separated by a single space. It means there is a bidirectional road between u and v with the cost of time w. There may be multiple roads between two cities.
Then for each case: an integer n (2<=n<=1000) means the number of city in the magical world, the cities are numbered from 1 to n. Then an integer m means the roads in the magical world, m (0< m <=50000). Following m lines, each line with three integer u, v, w (u != v,1 <=u, v<=n, 1<=w <1000), separated by a single space. It means there is a bidirectional road between u and v with the cost of time w. There may be multiple roads between two cities.
Output
Each case per line: the shortest time to reach city n in the worst case. If it is impossible to reach city n in the worst case, output “-1”.
Sample Input
3
4
4
1 2 5
2 4 10
1 3 3
3 4 8
3
2
1 2 5
2 3 10
2
2
1 2 1
1 2 2
4
4
1 2 5
2 4 10
1 3 3
3 4 8
3
2
1 2 5
2 3 10
2
2
1 2 1
1 2 2
Sample Output
15
-1
2
-1
2
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std; const int N=1010;
const int M=100010;
const int INF=0xffffff; struct Edge
{
int u;
int to;
int w;
int flag;
int next;
} e[M]; int head[N];
int dist[N];
int path[N];
int inq[N];
int n,m,cnt,flag; void AddEdge(int u,int v,int w)
{
e[cnt].u=u;
e[cnt].to=v;
e[cnt].w=w;
e[cnt].flag=1;
e[cnt].next=head[u];
head[u]=cnt++;
} int SPFA(int s)
{
queue<int>Q;
for(int i=1; i<=n; i++)
{
dist[i]=INF;
inq[i]=0;
}
dist[s]=0;
inq[s]=1;
Q.push(s);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
inq[u]=0;
for(int j=head[u]; j!=-1; j=e[j].next)
{
int x=e[j].to;
if(e[j].flag&&dist[x]>dist[u]+e[j].w)
{
dist[x]=dist[u]+e[j].w;
if(!flag)
path[x]=j;
if(!inq[x])
{
Q.push(x);
inq[x]=1;
}
}
}
}
return dist[n];
} int main()
{
//freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--)
{
cnt=flag=0;
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);
while(m--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
AddEdge(u,v,w);
AddEdge(v,u,w);
}
memset(path,-1,sizeof(path));
SPFA(1);
flag=1;
int i=n,j=-1;
int res=-1;
while(path[i]!=-1)
{
j=path[i];
e[j].flag=e[j+1].flag=0;
int tmp=SPFA(1);
e[j].flag=e[j+1].flag=1;
if(tmp>res)
res=tmp;
i=e[j].u;
}
if(res<INF)
printf("%d\n",res);
else
puts("-1");
}
}
最新文章
- Docker知识-1
- MapReduce 过程分析
- CocoSocket开源下载与编写经验分享
- 使用Web.Config Transformation配置灵活的配置文件
- js012-DO2和DOM3
- Auty自动化测试框架第七篇——添加动作库和常量文件库
- 字符串长度函数strlen()
- 向数据库中添加内容 manageStdInfo.aspx
- 《Head First 设计模式》ch.3 装饰(Decorator)模式
- python命令行参数处理模块 optparse 使用参考
- MySQL常用命令总结3
- GPUImage的filter 响应处理链 的理解笔记
- Android5.1 - 通讯录建立群组
- JVM基础系列第13讲:JVM参数之追踪类信息
- loc iloc函数的区别
- react-redux-reducer
- Python之推导式、生成器表达式
- 数据库范式:1NF,2NF,3NF,BCNF浅析
- busybox linux-2.6.2 编译安装中碰到的若干问题
- Python 函数(可变参数)