首页 > 代码库 > POJ 3255 && HDU 1688 && HDU 3191 次短路问题
POJ 3255 && HDU 1688 && HDU 3191 次短路问题
POJ 3255
Roadblocks
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 7627 | Accepted: 2798 |
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
Line 1: Two space-separated integers: N and R
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)
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
Line 1: The length of the second shortest path between node 1 and node N
Sample Input
4 41 2 1002 4 2002 3 2503 4 100
Sample Output
450
题目意思：
给一个结点个数为n，边数为m的无向图，求1到n之间的次短路长度。
思路：
需要深刻理解dijkstra算法的贪心原理。普通点的dijkstra算法是用一个结点k的最短路径更新与k相连没被visited的结点的最短路径。
那么同理也可以更新次短路经。
1到一个结点k的最短路径或可以更新与k相连结点j的最短路径或次短路经。
当遍历到k时，此时没被遍历过的最短路径结点为k的最短路径或者k的次短路经。设dis[k][mark]为遍历到k时最短路径或次短路经(mark=1时为k的最短路径，mark为2时为k的次短路经)，与k相连的没有被遍历过得结点为j,w为k与j之间一条边的权值。
那么
若dis[j][1]>dis[k][mark]+w时更新j的最短路径长度(及个数，HDU3191会用到，代码中也加了更新个数的代码，在本题中可以删去),次短路经长度（及个数）。
若dis[j][1]==dis[k][mark]+w时更新j的最短路径个数。
若dis[j][1]<dis[k][mark]+w<dis[j][2]更新j的次短路经长度及个数。
若dis[j][2]==dis[k][mark]+w时更新j的次短路经个数。
代码：
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 9 #define N 500510 #define inf 199999999911 12 struct mem{13 int y, w;14 };15 16 vector<mem>ve[N];17 int n, m;18 int dis[N][3];19 int visited[N][3];20 int num[N][3];21 int S, E;22 23 void dijkstra(){24 int i, j;25 int u, ma;26 mem p, q;27 memset(visited,0,sizeof(visited));28 memset(num,0,sizeof(num));29 for(i=0;i<=n;i++){30 for(j=1;j<=2;j++)31 dis[i][j]=inf;32 }33 dis[S][1]=0;num[S][1]=1;34 for(i=0;i<2*n;i++){35 int tmp=inf;36 for(j=1;j<=n;j++){37 if(!visited[j][1]&&dis[j][1]<tmp){38 u=j;ma=1;tmp=dis[j][1];39 }40 else if(!visited[j][2]&&dis[j][2]<tmp){41 u=j;ma=2;tmp=dis[j][2];42 }43 }44 if(tmp==inf) break;45 visited[u][ma]=1;46 for(j=0;j<ve[u].size();j++){47 p=ve[u][j];48 if(dis[p.y][1]>dis[u][ma]+p.w){49 dis[p.y][2]=dis[p.y][1];50 num[p.y][2]=num[p.y][1];51 dis[p.y][1]=dis[u][ma]+p.w;52 num[p.y][1]=num[u][ma];53 }54 else if(dis[p.y][1]==dis[u][ma]+p.w){55 num[p.y][1]+=num[u][ma];56 }57 else if(dis[p.y][2]>dis[u][ma]+p.w){58 dis[p.y][2]=dis[u][ma]+p.w;59 num[p.y][2]=num[u][ma];60 }61 else if(dis[p.y][2]==dis[u][ma]+p.w){62 num[p.y][2]+=num[u][ma];63 }64 }65 }66 }67 main()68 {69 int i, j, t;70 mem p;71 int x, y, z;72 73 while(scanf("%d %d",&n,&m)==2){74 75 for(i=0;i<=n;i++) ve[i].clear();76 while(m--){77 scanf("%d %d %d",&x,&y,&z);78 p.y=y;p.w=z;79 ve[x].push_back(p);80 p.y=x;81 ve[y].push_back(p);82 }83 S=1;E=n;84 dijkstra();85 printf("%d\n",dis[n][2]);86 } 87 }
HDU 3191
How Many Paths Are There
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1115 Accepted Submission(s): 377
Problem Description
oooccc1 is a Software Engineer who has to ride to the work place every Monday through Friday. For a long period, he went to office with the shortest path because he loves to sleep late…Time goes by, he find that he should have some changes as you could see, always riding with the same path is boring.
One day, oooccc1 got an idea! Why could I take another path? Tired at all the tasks he got, he got no time to carry it out. As a best friend of his, you’re going to help him!
Since oooccc1 is now getting up earlier, he is glad to take those paths, which are a little longer than the shortest one. To be precisely, you are going to find all the second shortest paths.
You would be given a directed graph G, together with the start point S which stands for oooccc’1 his house and target point E presents his office. And there is no cycle in the graph. Your task is to tell him how long are these paths and how many there are.
One day, oooccc1 got an idea! Why could I take another path? Tired at all the tasks he got, he got no time to carry it out. As a best friend of his, you’re going to help him!
Since oooccc1 is now getting up earlier, he is glad to take those paths, which are a little longer than the shortest one. To be precisely, you are going to find all the second shortest paths.
You would be given a directed graph G, together with the start point S which stands for oooccc’1 his house and target point E presents his office. And there is no cycle in the graph. Your task is to tell him how long are these paths and how many there are.
Input
There are some cases. Proceed till the end of file.
The first line of each case is three integers N, M, S, E (3 <= N <= 50, 0 <= S , E <N)
N stands for the nodes in that graph, M stands for the number of edges, S stands for the start point, and E stands for the end point.
Then M lines follows to describe the edges: x y w. x stands for the start point, and y stands for another point, w stands for the length between x and y.
All the nodes are marked from 0 to N-1.
The first line of each case is three integers N, M, S, E (3 <= N <= 50, 0 <= S , E <N)
N stands for the nodes in that graph, M stands for the number of edges, S stands for the start point, and E stands for the end point.
Then M lines follows to describe the edges: x y w. x stands for the start point, and y stands for another point, w stands for the length between x and y.
All the nodes are marked from 0 to N-1.
Output
For each case,please output the length and count for those second shortest paths in one line. Separate them with a single space.
Sample Input
3 3 0 2
0 2 5
0 1 4
1 2 2
Sample Output
6 1
题目意思：
给一个结点个数为n，边数为m的有向图，给起始点s和终点e。求s到e的次短路经长度及个数。
思路：
和上个代码基本一样，改一下数据范围和输出即可。
代码：
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 9 #define N 5510 #define inf INT_MAX11 12 struct mem{13 int y, w;14 };15 16 vector<mem>ve[N];17 int n, m;18 int dis[N][3];19 int visited[N][3];20 int num[N][3];21 int S, E;22 23 void dijkstra(){24 int i, j;25 int u, ma;26 mem p, q;27 memset(visited,0,sizeof(visited));28 memset(num,0,sizeof(num));29 for(i=0;i<=n;i++){30 for(j=1;j<=2;j++)31 dis[i][j]=inf;32 }33 dis[S][1]=0;num[S][1]=1;34 for(i=0;i<2*n;i++){35 int tmp=inf;36 for(j=0;j<n;j++){37 if(!visited[j][1]&&dis[j][1]<tmp){38 u=j;ma=1;tmp=dis[j][1];39 }40 else if(!visited[j][2]&&dis[j][2]<tmp){41 u=j;ma=2;tmp=dis[j][2];42 }43 }44 if(tmp==inf) break;45 if(visited[u][ma]) continue;46 visited[u][ma]=1;47 for(j=0;j<ve[u].size();j++){48 p=ve[u][j];49 if(dis[p.y][1]>dis[u][ma]+p.w){50 dis[p.y][2]=dis[p.y][1];51 num[p.y][2]=num[p.y][1];52 dis[p.y][1]=dis[u][ma]+p.w;53 num[p.y][1]=num[u][ma];54 }55 else if(dis[p.y][1]==dis[u][ma]+p.w){56 num[p.y][1]+=num[u][ma];57 }58 else if(dis[p.y][2]>dis[u][ma]+p.w){59 dis[p.y][2]=dis[u][ma]+p.w;60 num[p.y][2]=num[u][ma];61 }62 else if(dis[p.y][2]==dis[u][ma]+p.w){63 num[p.y][2]+=num[u][ma];64 }65 }66 }67 68 }69 main()70 {71 int i, j;72 mem p;73 int x, y, z;74 while(scanf("%d %d %d %d",&n,&m,&S,&E)==4){75 for(i=0;i<=n;i++) ve[i].clear();76 while(m--){77 scanf("%d %d %d",&x,&y,&z);78 p.y=y;p.w=z;79 ve[x].push_back(p);80 }81 dijkstra();82 printf("%d %d\n",dis[E][2],num[E][2]);83 } 84 }
HDU 1688
Sightseeing
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 677 Accepted Submission(s): 272
Problem Description
Tour operator Your Personal Holiday organises guided bus trips across the Benelux. Every day the bus moves from one city S to another city F. On this way, the tourists in the bus can see the sights alongside the route travelled. Moreover, the bus makes a number of stops (zero or more) at some beautiful cities, where the tourists get out to see the local sights.
Different groups of tourists may have different preferences for the sights they want to see, and thus for the route to be taken from S to F. Therefore, Your Personal Holiday wants to offer its clients a choice from many different routes. As hotels have been booked in advance, the starting city S and the final city F, though, are fixed. Two routes from S to F are considered different if there is at least one road from a city A to a city B which is part of one route, but not of the other route.
There is a restriction on the routes that the tourists may choose from. To leave enough time for the sightseeing at the stops (and to avoid using too much fuel), the bus has to take a short route from S to F. It has to be either a route with minimal distance, or a route which is one distance unit longer than the minimal distance. Indeed, by allowing routes that are one distance unit longer, the tourists may have more choice than by restricting them to exactly the minimal routes. This enhances the impression of a personal holiday.
For example, for the above road map, there are two minimal routes from S = 1 to F = 5: 1 → 2 → 5 and 1 → 3 → 5, both of length 6. There is one route that is one distance unit longer: 1 → 3 → 4 → 5, of length 7.
Now, given a (partial) road map of the Benelux and two cities S and F, tour operator Your Personal Holiday likes to know how many different routes it can offer to its clients, under the above restriction on the route length.
Different groups of tourists may have different preferences for the sights they want to see, and thus for the route to be taken from S to F. Therefore, Your Personal Holiday wants to offer its clients a choice from many different routes. As hotels have been booked in advance, the starting city S and the final city F, though, are fixed. Two routes from S to F are considered different if there is at least one road from a city A to a city B which is part of one route, but not of the other route.
There is a restriction on the routes that the tourists may choose from. To leave enough time for the sightseeing at the stops (and to avoid using too much fuel), the bus has to take a short route from S to F. It has to be either a route with minimal distance, or a route which is one distance unit longer than the minimal distance. Indeed, by allowing routes that are one distance unit longer, the tourists may have more choice than by restricting them to exactly the minimal routes. This enhances the impression of a personal holiday.
For example, for the above road map, there are two minimal routes from S = 1 to F = 5: 1 → 2 → 5 and 1 → 3 → 5, both of length 6. There is one route that is one distance unit longer: 1 → 3 → 4 → 5, of length 7.
Now, given a (partial) road map of the Benelux and two cities S and F, tour operator Your Personal Holiday likes to know how many different routes it can offer to its clients, under the above restriction on the route length.
Input
The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:
One line with two integers N and M, separated by a single space, with 2 ≤ N ≤ 1,000 and 1 ≤ M ≤ 10, 000: the number of cities and the number of roads in the road map.
M lines, each with three integers A, B and L, separated by single spaces, with 1 ≤ A, B ≤ N, A ≠ B and 1 ≤ L ≤ 1,000, describing a road from city A to city B with length L.
The roads are unidirectional. Hence, if there is a road from A to B, then there is not necessarily also a road from B to A. There may be different roads from a city A to a city B.
One line with two integers S and F, separated by a single space, with 1 ≤ S, F ≤ N and S ≠ F: the starting city and the final city of the route.
There will be at least one route from S to F.
One line with two integers N and M, separated by a single space, with 2 ≤ N ≤ 1,000 and 1 ≤ M ≤ 10, 000: the number of cities and the number of roads in the road map.
M lines, each with three integers A, B and L, separated by single spaces, with 1 ≤ A, B ≤ N, A ≠ B and 1 ≤ L ≤ 1,000, describing a road from city A to city B with length L.
The roads are unidirectional. Hence, if there is a road from A to B, then there is not necessarily also a road from B to A. There may be different roads from a city A to a city B.
One line with two integers S and F, separated by a single space, with 1 ≤ S, F ≤ N and S ≠ F: the starting city and the final city of the route.
There will be at least one route from S to F.
Output
For every test case in the input file, the output should contain a single number, on a single line: the number of routes of minimal length or one distance unit longer. Test cases are such, that this number is at most 10^9 = 1,000,000,000.
Sample Input
2
5 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5
5 6
2 3 1
3 2 1
3 1 10
4 5 2
5 2 7
5 2 7
4 1
Sample Output
3
2
题目意思：
给一个结点个数为n，边数为m的有向图，给起始点s和终点e，求s到e的最短路径个数和比最短路径大1的次短路经个数之和。
思路：
和上面代码基本一样，改一下就行了。
代码：
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 9 #define N 100510 #define inf INT_MAX11 12 struct mem{13 int y, w;14 };15 16 vector<mem>ve[N];17 int n, m;18 int dis[N][3];19 int visited[N][3];20 int num[N][3];21 int S, E;22 23 void dijkstra(){24 int i, j;25 int u, ma;26 mem p, q;27 memset(visited,0,sizeof(visited));28 memset(num,0,sizeof(num));29 for(i=0;i<=n;i++){30 for(j=1;j<=2;j++)31 dis[i][j]=inf;32 }33 dis[S][1]=0;num[S][1]=1;34 for(i=0;i<2*n;i++){35 int tmp=inf;36 for(j=1;j<=n;j++){37 if(!visited[j][1]&&dis[j][1]<tmp){38 u=j;ma=1;tmp=dis[j][1];39 }40 else if(!visited[j][2]&&dis[j][2]<tmp){41 u=j;ma=2;tmp=dis[j][2];42 }43 }44 if(tmp==inf) break;45 visited[u][ma]=1;46 for(j=0;j<ve[u].size();j++){47 p=ve[u][j];48 if(dis[p.y][1]>dis[u][ma]+p.w){49 dis[p.y][2]=dis[p.y][1];50 num[p.y][2]=num[p.y][1];51 dis[p.y][1]=dis[u][ma]+p.w;52 num[p.y][1]=num[u][ma];53 }54 else if(dis[p.y][1]==dis[u][ma]+p.w){55 num[p.y][1]+=num[u][ma];56 }57 else if(dis[p.y][2]>dis[u][ma]+p.w){58 dis[p.y][2]=dis[u][ma]+p.w;59 num[p.y][2]=num[u][ma];60 }61 else if(dis[p.y][2]==dis[u][ma]+p.w){62 num[p.y][2]+=num[u][ma];63 }64 }65 }66 }67 main()68 {69 int i, j, t;70 mem p;71 int x, y, z;72 73 cin>>t;74 while(t--){75 scanf("%d %d",&n,&m);76 for(i=0;i<=n;i++) ve[i].clear();77 while(m--){78 scanf("%d %d %d",&x,&y,&z);79 p.y=y;p.w=z;80 ve[x].push_back(p);81 }82 scanf("%d %d",&S,&E);83 dijkstra();84 if(dis[E][2]==dis[E][1]+1) printf("%d\n",num[E][1]+num[E][2]);85 else printf("%d\n",num[E][1]);86 } 87 }
POJ 3255 && HDU 1688 && HDU 3191 次短路问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。