codevs1021 玛丽卡
2024-10-13 01:41:34
题目描述 Description
麦克找了个新女朋友,玛丽卡对他非常恼火并伺机报复。
因为她和他们不住在同一个城市,因此她开始准备她的长途旅行。
在这个国家中每两个城市之间最多只有一条路相通,并且我们知道从一个城市到另一个城市路上所需花费的时间。
麦克在车中无意中听到有一条路正在维修,并且那儿正堵车,但没听清楚到底是哪一条路。无论哪一条路正在维修,从玛丽卡所在的城市都能到达麦克所在的城市。
玛丽卡将只从不堵车的路上通过,并且她将按最短路线行车。麦克希望知道在最糟糕的情况下玛丽卡到达他所在的城市需要多长时间,这样他就能保证他的女朋友离开该城市足够远。
编写程序,帮助麦克找出玛丽卡按最短路线通过不堵车道路到达他所在城市所需的最长时间(用分钟表示)。
输入描述 Input Description
第一行有两个用空格隔开的数N和M,分别表示城市的数量以及城市间道路的数量。1≤N≤1000,1≤M≤N*(N-1)/2。城市用数字1至N标识,麦克在城市1中,玛丽卡在城市N中。
接下来的M行中每行包含三个用空格隔开的数A,B和V。其中1≤A,B≤N,1≤V≤1000。这些数字表示在A和城市B中间有一条双行道,并且在V分钟内是就能通过。
输出描述 Output Description
输出文件的第一行中写出用分钟表示的最长时间,在这段时间中,无论哪条路在堵车,玛丽卡应该能够到达麦克处,如果少于这个时间的话,则必定存在一条路,该条路一旦堵车,玛丽卡就不能够赶到麦克处。
样例输入 Sample Input
5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10
样例输出 Sample Output
27
/*
次短路,其与最短路至少有一条边不同,于是枚举次短路上的每一条边
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define ll long long
using namespace std;
const int maxn = ;
const ll inf = 987654321234LL;
int read(){
char ch=getchar();
int x=,f=;
while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};
while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};
return x*f;
}
struct edge{
int u;
int v;
int w;
int id;
int nxt;
}e[maxn*maxn];
int n,m;
int head[maxn],cnt;
ll dis[maxn],ans;
int vis[maxn],flag,cut_e,frm[maxn];
void ins(int u,int v,int w,int t){
cnt++;
e[cnt].u = u;
e[cnt].v = v;
e[cnt].w = w;
e[cnt].id = t;
e[cnt].nxt = head[u];
head[u] = cnt;
}
void spfa(bool cmd){
flag++;
queue<int> q;
int now,to;
for(int i = ;i <= n;i++) dis[i] = inf;
dis[] = ;
vis[] = flag;
q.push();
while(!q.empty()){
now = q.front();
q.pop();
for(int i = head[now];i;i = e[i].nxt){
if(cmd && e[i].id == cut_e) continue;
to = e[i].v;
if(dis[to] > dis[now] + e[i].w){
dis[to] = dis[now] + e[i].w;
if(!cmd) frm[to] = i;
if(vis[to] != flag){
vis[to] = flag;
q.push(to);
}
}
}
vis[now] = ;
}
}
int main(){
n = read();
m = read();
int a,b,v;
for(int i = ;i <= m;i++){
a = read();
b = read();
v = read();
ins(a,b,v,i);
ins(b,a,v,i);
}
spfa(false);
for(int i = n;i != ;i = e[frm[i]].u){
cut_e = e[frm[i]].id;
spfa(true);
ans = max(ans,dis[n]);
}
cout<<ans;
return ;
}
最新文章
- ES6中的var let const应如何选择
- 【转】C# 中的委托和事件
- 【编程题目】在从 1 到 n 的正数中 1 出现的次数
- 【bzoj1053】反素数
- SSH Spring3\Java1.8 “Unable to instantiate Action, xxAction, defined for &#39;xxAction_login&#39; in namespace &#39;/&#39;null”
- 【转】预编译头文件来自编译器的早期版本,或者预编译头为 C++ 而在 C 中使用它(或相反)
- HashMap在Android和Java中的不同实现
- Maven安装中的问题
- checkbox属性checked=";checked";但状态不是勾选状态的解决办法
- CALayer的隐式动画和显式动画
- Java 快排
- Python开发者现实版养成路线:从一无所知到无所不知
- new Date() 日期格式处理
- Bytom BIP-32协议和BIP-44协议
- android json 解析简单实例
- JavaScript FormData的详细介绍及使用
- 基于Spring-Cloud的微服务框架设计
- Django的Modelforms的介绍
- Android定位测试(深坑)
- 旋转数组的最小数字(C++ 和 Python 实现)
热门文章
- pacemaker+corosync/heartbeat对比及资源代理RA脚本
- BZOJ1878: [SDOI2009]HH的项链[树状数组 离线]
- NOIP模拟赛20161114
- 错误提示:LINK : fatal error LNK1123: failure during conversion to COFF: file invalid or corrupt 的解决方法
- Python-05-常用模块
- npoi批量导入实现及相关技巧
- MVC5 + EF6 + Bootstrap3 (16) 客户端验证
- ASP.NET中的缓存机制
- 数据结构图文解析之:直接插入排序及其优化(二分插入排序)解析及C++实现
- Mysql服务启动的时候 如何加载配置文件