POJ 3255 Roadblocks (次短路模板)
Time Limit: 2000MS | Memory Limit: 65536K | |
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 intersectionN.
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<queue>
#include<cstdio>
#include<cstring>
#define N 5001
#define M 100001
using namespace std;
int front[N],to[M<<],nxt[M<<],val[M<<],from[M<<],tot;
int dis1[N],dis2[N];
bool vis[N];
queue<int>q;
void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w; from[tot]=u;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; val[tot]=w; from[tot]=v;
}
void spfa(int s,int *dis)
{
//memset(dis,63,sizeof(dis));
memset(vis,false,sizeof(vis));
q.push(s);
vis[s]=true;
dis[s]=;
int now;
while(!q.empty())
{
now=q.front();
q.pop();
vis[now]=false;
for(int i=front[now];i;i=nxt[i])
if(dis[to[i]]>dis[now]+val[i])
{
dis[to[i]]=dis[now]+val[i];
if(!vis[to[i]])
{
vis[to[i]]=true;
q.push(to[i]);
}
}
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int u,v,w;
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
memset(dis1,,sizeof(dis1));
memset(dis2,,sizeof(dis2));
spfa(,dis1);
spfa(n,dis2);
int minn=dis1[n],tmp,ans=0x7fffffff;
for(int i=;i<=tot;i++)
{
u=from[i]; v=to[i];
tmp=dis1[u]+val[i]+dis2[v];
if(tmp>minn && tmp<ans) ans=tmp;
}
printf("%d",ans);
}
最新文章
- java 关键字 assert的学习
- Git随记
- 【Tech】Ganglia安装配置
- 内部技术分享的 PPT
- php集成开发环境IDE
- 转: android编译过程(流程图)
- IBUS-WARNING **: Process Key Event failed: Timeout was reached
- 折腾iPhone的生活——iPhone 5s 开启 assistive touch 后卡顿的问题
- mycat实例(1)
- 进入MFC讲坛的前言(二)
- [转载]John Burkardt搜集的FORTRAN源代码
- 同一台PC,配置多个同一存储平台下的Git账号【两个码云账号,配置在同一台PC上】
- 使用 jest 测试 react component 的配置,踩坑。
- 编织织物的knit course direction and knit wale direction
- M1/M2 总结
- ransom-note
- Idea2016配置并破解jrebel
- slam学习
- 每天一个linux命令(磁盘):【转载】du 命令
- 【Qt开发】01-第一个Qt程序Hello World!
热门文章
- IntelliJ IDEA 2017.3/2018.1/.2 激活
- POJ 1741 Tree(树的分治)
- 我的Vscode配置
- cp的使用
- Thunder团队第三周 - Scrum会议5
- 团队作业week9 情景测试
- vs调试时报503错误
- iOS- 如何将非ARC的项目转换成ARC项目(实战)
- Spring Boot(四)@EnableXXX注解分析
- java.lang.ClassNotFoundException: com.google.gson.Gson 问题解决