1099 - Not the Best
Time Limit:2 second(s)
|
Memory Limit:32 MB
|
Robin has moved to a small village and sometimes enjoys returning to visit one of his best friends. He does not want to get to his old home too quickly, because he likes the scenery along the way. He has decided to take the second-shortest rather than the
shortest path. He knows there must be some second-shortest path.
The countryside consists ofRbidirectional roads, each linking two of theNintersections, conveniently numbered from1toN. Robin starts at intersection1, and his 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
Input starts with an integerT (≤ 10), denoting the number of test cases.
Each case contains two integersN (1 ≤ N ≤ 5000)andR (1 ≤ R ≤ 105). Each of the nextRlines contains three space-separated integers:u, vandwthat describe
a road that connects intersectionsuandvand has lengthw (1 ≤ w ≤ 5000).
Output
For each case, print the case number and the second best shortest path as described above.
Sample Input
|
Output for Sample Input
|
2
3 3
1 2 100
2 3 200
1 3 50
4 4
1 2 100
2 4 200
2 3 250
3 4 100
|
Case 1: 150
Case 2: 450
|
PROBLEM SETTER: JANE ALAM JAN
传送门:http://lightoj.com/volume_showproblem.php?problem=1099
题意:对第2短路做了一个新的定义,如果存在多条最短路,那么一条比最短路长,而且比其他所有路径短的路径才是第2短路。
思路:和上一题差不多,直接用A*,然后改变退出条件即可,即 cur.f > dist[src]
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN = 5555,MAXM = 111111;
int inQ[MAXN],dist[MAXN],t,n,m,head[MAXN],ecnt;
struct edge{
int v,w,nxt;
edge(){nxt=-1;}
edge(int vv,int ww,int nx):v(vv),w(ww),nxt(nx){}
}next[MAXM<<1];
void init(){
memset(inQ,0,sizeof(inQ));
fill(dist,dist+MAXN,0x3fffffff);
memset(head,-1,sizeof(head));
ecnt = 0;
}
void add(int u,int v,int w){
next[ecnt++] = edge(v,w,-1);
next[ecnt++] = edge(u,w,-1);
next[ecnt-2].nxt = head[u];
head[u] = ecnt-2;
next[ecnt-1].nxt = head[v];
head[v] = ecnt-1;
}
struct node{
int f,g,v;
node(){}
node(int ff,int gg,int vv):f(ff),g(gg),v(vv){}
bool operator < (const node &n) const{
return n.f < f;
}
};
void spfa(int src){
queue<int> Q;
Q.push(src);
inQ[src] = 1;
dist[src] = 0;
while(!Q.empty()){
int now = Q.front();
Q.pop();inQ[now]=0;
for(int i=head[now];i!=-1;i=next[i].nxt){
if(dist[next[i].v]>dist[now]+next[i].w){
dist[next[i].v] = dist[now]+next[i].w;
if(!inQ[next[i].v]){
inQ[next[i].v]=1;
Q.push(next[i].v);
}
}
}
}
}
int Astar(int src){
priority_queue<node> PQ;
memset(inQ,0,sizeof(inQ));
PQ.push(node(dist[src],0,src));
while(!PQ.empty()){
node cur = PQ.top();
PQ.pop();inQ[cur.v]++;
//cout<<cur.f<<endl;
if(cur.f>dist[src]){
return cur.f;
}
for(int i=head[cur.v];i!=-1;i=next[i].nxt){
node expand(cur.g+dist[next[i].v]+next[i].w,cur.g+next[i].w,next[i].v);
PQ.push(expand);
}
}
return -1;
}
int main(){
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
scanf("%d%d",&n,&m);
init();
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);a--,b--;
add(a,b,c);
}
spfa(n-1);
printf("Case %d: %d\n",cas,Astar(0));
}
return 0;
}
分享到:
相关推荐
LightOJ-已解决代码我所有的Light Online Judge的解决问题代码。
轻描淡写 像Codeforces编辑模式一样在lightoj上发表社论!
LightOJ-solutions
LightOJ
2. BNU 1440 --- basic dfs 3. POJ 1190 --- dfs + pruning(Strong) 4. UVALive 2243 --- dfs 5. FZU 2196 --- double bfs 6. PKU 1426 --- bfs + pruning 7. BNU 1038 --- dfs transform 8. PKU 1562 --- dfs ...
解析编程问题,并将其发送给CHelper插件以实现IntelliJ IDEA。 竞争性伴侣解析程序...-HackerRank-HDU在线法官-Kattis-LightOJ-NYTD在线法官-PEG法官-POJ-QDUOJ-Timus-URI在线法官 支持语言:English (United States)
问题教程:一个包含有关LightOJ问题的教程的存储库
2 和 c 动态规划 动态规划相关问题的解答。 这些问题来自各种在线评委,包括 、 、 等。 解决方案是用 C++ 编码的。 —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
光OJ 收集我在发现的一些问题的解决方案
已解决的编程问题 Online Judges 这个存储库包含我解决的各种在线法官的编程问题的解决方案,即 UVa、Topcoder、Codeforces、Hackerrank、LightOj、Spoj、Project Euler 等。
这是乔杜里医学博士。 伊斯玛姆·拉赫曼(Ishmam Rahman) :closed_mailbox_with_raised_flag: 联络我: ... LightOJ: ://lightoj.com/user/ishmam64 脸书: : 目标:使自己在新技术的海洋中立足,在这里我可
描述在这里,您可以从uva,lightoj,spoj,timus等不同的在线法官那里找到我解决的问题。
race_words = [“后缀数组”,“前缀特里”,“动态编程”,“竞赛”,“ codeforces”,“编程”,“竞争性编程”,“算法”,“数据结构”,“ codeforces”,“ light oj”,“ lightoj”,“ spoj”,“堆栈”,...
开心农场java源码AA Noman Ansary 你好呀! 我的名字是AA Noman Ansary 。 但我更喜欢被称为Showrav...问题解决:LightOJ。 代码部队。 蒂姆斯。 紫外线。 成就 以下是我的一些显著成就: BRAC 大学副校长证书。 (2019)
这个仓库是关于什么的 创建该存储库是为了组织与数据结构和算法有关的问题的解决方案。 并且,如果可能的话,为学习与数据结构和算法有关的各种概念提供一种更简单的方法。 以下评委使用的问题 ...
测试程序TestProgram 是针对竞争性编程程序(即 Codeforces、lightOJ、OmegaUp 等)的专用测试工具。 当我们解决问题时,我们必须非常小心,并致力于解决所有可能的情况。 我们的解决方案在登顶前正确解决的测试用例...
problemSolving