poj3255

关键词：

题目链接：http://poj.org/problem?id=3255

解题思路：

　　昨晚两点多睡不着翻起来刷《挑战》的题，结果遇到这道求次短路的题，一脸懵逼。想了半小时没什么思路就看他的解答了。具体看代码吧，讲解可以参考《挑战程序设计竞赛》P119。其实还是Dijkstra算法的变形。但是这个变形确实不太好想。

AC代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 #include <queue>
 5 using namespace std;
 6 typedef pair<int,int> P;
 7 const int maxn=5000+3,inf=0x7ffffff;
 8 struct edge{
 9     int to,cost;
10 };
11 vector<edge> G[maxn];
12 int d[maxn],d2[maxn];
13 int main()
14 {
15     int N,R,A,B,D;
16     scanf("%d%d",&N,&R);
17     while(R--){
18         scanf("%d%d%d",&A,&B,&D);
19         edge temp;
20         temp.cost=D;
21         temp.to=B;  G[A].push_back(temp);
22         temp.to=A;  G[B].push_back(temp);
23     }
24     priority_queue<P,vector<P>,greater<P> > que;
25     for(int i=1;i<=N;i++)   d[i]=d2[i]=inf;
26     d[1]=0;
27     que.push(P(0,1));
28     while(!que.empty()){
29         P p=que.top();  que.pop();
30         int v=p.second;
31         if(d2[v]<p.first)   continue;       //如果次短路都比此短，那么就没有更新的必要了
32         for(int i=0;i<G[v].size();i++){
33             edge e=G[v][i];
34             int dt=p.first+e.cost;     //一开始那个p.first被我携程d[v]了，很显然有bug
35             if(d[e.to]>dt){
36                 swap(d[e.to],dt);
37                 que.push(P(d[e.to],e.to));
38             }
39             if(d2[e.to]>dt&&dt>d[e.to]){
40                 d2[e.to]=dt;
41                 que.push(P(d2[e.to],e.to));
42             }
43         }
44     }
45     printf("%d
",d2[N]);
46 
47     return 0;
48 }

poj3255roadblocks

RoadblocksTimeLimit: 2000MS MemoryLimit: 65536KTotalSubmissions: 13216 Accepted: 4660DescriptionBessiehasmovedtoasmallfarmandsometimesenjoysreturningtovisitoneofherbestfr 查看详情

poj3255roadblocks

RoadblocksTimeLimit: 2000MS MemoryLimit: 65536KTotalSubmissions: 13594 Accepted: 4783DescriptionBessiehasmovedtoasmallfarmandsometimesenjoysreturningtovisitoneofherbestfr 查看详情

poj3255

poj3255题意：输入u,r表示有n个点，r条无向边输出1到n的次短路。题解：单源最短路，使用优先队列优化。模板题。#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<vector>#include<map>#include&l 查看详情

次短路poj3255(代码片段)

 DescriptionBessiehasmovedtoasmallfarmandsometimesenjoysreturningtovisitoneofherbestfriends.Shedoesnotwanttogettoheroldhometooquickly,becauseshelikesthesceneryalongtheway.Shehasdecidedtotakethese 查看详情

poj3255

题目链接：http://poj.org/problem?id=3255解题思路：　　昨晚两点多睡不着翻起来刷《挑战》的题，结果遇到这道求次短路的题，一脸懵逼。想了半小时没什么思路就看他的解答了。具体看代码吧，讲解可以参考《挑战程序设计竞赛》... 查看详情

poj3255roadblocks[次短路]

RoadblocksTimeLimit: 2000MS MemoryLimit: 65536KTotalSubmissions: 12697 Accepted: 4491DescriptionBessiehasmovedtoasmallfarmandsometimesenjoysreturningtovisitoneofherbestfr 查看详情

poj3255

 1#include<iostream>2#include<queue>3#defineINF10000004usingnamespacestd;5typedefpair<int,int>P;//first是最短距离，second是顶点编号6structedge7{8intto,cost;9edge(inttt,intcc)10{11to=tt;12c 查看详情

[poj3255]次短路

给出一张有n个点和m条双向边的图，要求求出1到n的次短路的长度。一条边可以多次通过。输入格式：第一行为两个整数n和m。接下来的m行每行三个整数ai,bi,vi，分别表示这条路连着的两个点和他的长度。输出格式：一个整数，表... 查看详情

如何用求次长边——poj3255题解(代码片段)

...从1到n的次短路。其中(nle5000)，(mle100000)。题目传送门POJ3255思路其实求次长路是很简单的一个问题，但是网上却有很多算法都过于复杂了。首先我们先求出从1到每个结点的最短路长度（用Dijkstra或者是SPFA都可以）,存入数组(dis1)... 查看详情

roadlocks(poj3255)

1,直接上英文题目我果然不咋懂。2,这个edge了啥的用法我不清楚。 typedefpair<int,int>P;priority_queue<P,vector<P>,greater<P>>que; 把这个搞清楚下挺好的，“typedef为C语言的关键字,作用是为一种数据类型定义一个... 查看详情

3255:十进制到六进制-poj

3255:十进制到六进制总时间限制: 1000ms 内存限制: 65536kB描述进制转换:将十进制(不超过int类型表示的范围)的数转换为六进制的数.输入输入为第一行是组数n，后面n行是需要进制转换的十进制数.输出进制转换后的n行六... 查看详情

poj-3255roadblocks

求次短路问题，方法类似于求单源最短路，不过本题是将单源最短路和次最短路一块求解 到某一点次最短路（eg：u）：假设最短路为s->v->u,次短路为s->v->u‘或s->v‘->u注：s->v‘表示s->v的次短路，v->u‘表... 查看详情

前端学习（3255）：react中动态初始化结果

     查看详情

luogup3255[jloi2013]地形生成动态规划(代码片段)

 出题人语文真好...各不相同的标号和高度=各不相同的标号+单独的高度... 第一问比较简单，考虑从大到小插入，在相同情况下，按关键值从小到大插入这样子，关键大的元素一定会影响到关键小的元素，不会漏统计插入$... 查看详情

aaa认证

...168.2.2255.255.255.0RADIUSServerNIC192.168.3.2255.255.255.0PCaNIC192.168.1.3255.255.255.0PCbNIC192.168.2.3255.255.255.0PCcNIC192.168.3.3255.255.255.0 配置过程a.在路由器R1上配置一个本地用户账号并且利用本地AAA通过console线和VTY连接认证R1(config)#usernameadmin1pass... 查看详情

poj刷题指南

OJ上的一些水题(可用来练手和增加自信)(POJ3299,POJ2159,POJ2739,POJ1083,POJ2262,POJ1503,POJ3006,POJ2255,POJ3094)初期:一.基本算法:枚举.(POJ1753,POJ2965)贪心(POJ1328,POJ2109,POJ2586)递归和分治法.递推.构造法.(POJ3295)模拟法.(POJ1068,POJ2632,POJ1573,POJ2993,POJ2996)... 查看详情

程序员必须掌握哪些算法

一.基本算法:枚举.(poj1753,poj2965)贪心(poj1328,poj2109,poj2586)递归和分治法.递推.构造法.(poj3295)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)二.图算法:图的深度优先遍历和广度优先遍历.最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,po... 查看详情

acm入门学啥

...信息学竞赛》。计划：ACM的算法（觉得很好，有层次感）POJ上的一些水题(可用来练手和增加自信)(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)初期:一.基本算法:(1)枚举.(poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和... 查看详情