Sightseeing-白红宇

Sightseeing

阅读量：6830 次

发布时间：2019-06-26

本文共 5609 字，大约阅读时间需要 18 分钟。

题目：

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.

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.

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⁹ = 1,000,000,000.

Sample Input

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

Hint

The first test case above corresponds to the picture in the problem description.

需要真正理解dijkstra算法。

题目已经给出了解题思想！

题目的意思就是求出有多少条最短路径和比最短路径的大一的路径条数；

我们可以定义一个数组来标记最短路和次短路，

定义标记数组vist二维的，定义一个dis的数组标记当前的最短路和次短路，每次都从dis未标记的路径采取

，dis可能是最短路也可能是次短路。

只有当还有路径才不会结束。然后对当前的最短路和次短路进行更新节点（以后的纯地杰斯特拉的思想做），

关键是定义一个二维数组来保存当前的最短路和次短路径长度。

因为的、路径的多少未知，只能考虑最不好的情况（n的节点就有2*n-1条路径（最短的次短）），

为了节省时间，所以要判断当前是否有路径可走。确保高效！

解题代码！不是copy的！但是也不是自己的！一开始想自己编的，老出错，最后照着人家的代码来编！

#include"stdio.h"

#include"string.h"

const int max=1000000000;

struct node

{

int v,val,next;

}E[100000];

int first[100000],n,m,s,t,dis[1005][2],dp[1005][2],vist[1005][2];

int dij()

{

int i,y,val,j;

memset(dp,0,sizeof(dp));

memset(vist,0,sizeof(vist));

for(i=1;i<=n;i++)

dis[i][0]=dis[i][1]=max;

dis[s][0]=0;dp[s][0]=1;

for(i=1;i<n*2;i++)

{

int mn=max,x,flag;

for(j=1;j<=n;j++)

{

if(!vist[j][0]&&mn>dis[j][0])

{

mn=dis[j][0];

x=j;

flag=0;

}

else if(!vist[j][1]&&mn>dis[j][1])

{

mn=dis[j][1];

x=j;

flag=1;

}

if(mn==max)

break;

vist[x][flag]=1;

for(j=first[x];j!=-1;j=E[j].next)

{

y=E[j].v;

val=E[j].val;

if(mn+val<dis[y][0])

{

dis[y][1]=dis[y][0];

dp[y][1]=dp[y][0];

dis[y][0]=mn+val;

dp[y][0]=dp[x][flag];

}

else if(mn+val==dis[y][0])

{

dp[y][0]+=dp[x][flag];

}

else if(mn+val<dis[y][1])

{

dis[y][1]=mn+val;

dp[y][1]=dp[x][flag];

}

else if(mn+val==dis[y][1])

{

dp[y][1]+=dp[x][flag];

}

if(dis[t][0]+1==dis[t][1])

return dp[t][0]+dp[t][1];

return dp[t][0];

}

int main()

{

int i,T,x,y,val;

scanf("%d",&T);

while(T--)

{

scanf("%d%d",&n,&m);

memset(first,-1,sizeof(first));

for(i=1;i<=m;i++)

{

scanf("%d%d%d",&x,&y,&val);

E[i].v=y;E[i].val=val;

E[i].next=first[x];

first[x]=i;

}

scanf("%d%d",&s,&t);

printf("%d\n",dij());

}

return 0;

}

还有就是人家的思想：

我们可以利用dijstra算法的思想，只需在其中进行一些改进即可。可以先定义一个二维的数组dist[N][2]。dist[i][0]代表源点S到点i的最短路，dist[i][1]代表源点S到点i的次短路。初始化dist[S][0]=0，其余的都初始化为无穷大。然后定义一个二维数组waynum[N][2]记录路径方法数，waynum[S][0]=1，其余初始为0。再定义一个标记数组vis[N][2]，初始vis[S][0]被标记已访问，其余未访问。采用dijstra算法的思想，每次从dist[N][2]中选择一个未被标记且值最小的点dist[v][flag]（可能这个值是这个点的最短路，也可能是次短路，只有当此点的最短路被标记了次才可能选中此点的次短路）。再用这个值val去更新此点的邻接点u。更新的方法如下：