POJ3255-Roadblocks(最短路)
Description
Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path.
The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1..N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N.
The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path).
Input
Lines 2..R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000)
Output
Sample Input
4 4
1 2 100
2 4 200
2 3 250
3 4 100
Sample Output
450
Hint
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int,int> P;
int main(){
int n,r;
cin>>n>>r;
vector<int> dis(n+);
vector<int> tdis(n+);
vector<vector<P> > road(n+);
for(int i=;i<r;i++){
int a,b,c;
cin>>a>>b>>c;
road[a].push_back(P(c,b));
road[b].push_back(P(c,a));
}
priority_queue<P,vector<P>,greater<P> > que;
fill(dis.begin(),dis.end(),INT_MAX);
fill(tdis.begin(),tdis.end(),INT_MAX);
que.push(P(,));
dis[]=;
while(!que.empty()){
P p=que.top();
que.pop();
int v=p.second;
if(tdis[v]<p.first)continue;
for(int i=;i<road[v].size();i++){
P q=road[v][i];
int to=q.second;
int cost=q.first;
int d=p.first+cost;
if(d<dis[to]){
swap(d,dis[to]);
que.push(P(dis[to],to));
}
if(d<tdis[to]&&dis[to]<d){
tdis[to]=d;
que.push(P(tdis[to],to));
}
}
}
cout<<tdis[n]<<endl;
return ;
}
最新文章
- js中,var 修饰变量名和不修饰的区别
- nuint笔记
- VB 2015 的 闭包(Closure)
- 中间人攻击破解HTTPS传输内容
- 对云风 cstring 第二次解析
- MSSQL系统表常用操作
- 记一次npapi插件无窗口(windowless )化下的妙巧思路然后解决问题的超爽体验过程
- 乐在其中设计模式(C#) - 提供者模式(Provider Pattern)
- Mediator - 中介者模式
- JS高程5.引用类型(5)Array类型的操作方法
- 基于vue2.0+vuex+localStorage开发的本地记事本
- 理解纯CSS画三角形
- [luogu2831][noip d2t3]愤怒的小鸟_状压dp
- [ExtJS5学习笔记]第十三节 Extjs5的Ext.each方法学习
- 使用Python统计函数绘制简单图形matplotlib
- AFN 请求报 415错误解决方案
- SQL Server 2008 management studio 无法连接到(local)解决方法
- 原生tab选项卡制作
- .NET本质论 实例
- Java项目持续集成检查项