『jzyzoj』 最优乘车

发表于 | 阅读次数:
字数统计: 1,009 字

这是一道图论题：

题面：

H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴上线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。
　　刘世纪最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路已士
可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几次后到达S公园。
　　现在用整数1,2,…N 给H城的所有的巴士站编号，约定这名旅客所在饭店的巴士站编号为1…S公园巴士站的编号为N。
　　写一个程序，帮助刘世纪寻找一个最优乘车方案,使他在从饭店乘车到S公园的过程
中换车的次数最少。

输入格式 Input Format;

第一行有两个数字M和N(1<=M<=100 1<N<=500），表
示开通了M条单程巴士线路，总共有N个车站。从第二行到第M刊行依次给出了第1条到
第M条巴士线路的信息。其中第i+1行给出的是第i条巴士线路的信息，从左至右按运行顺序依次给出了该线路上的所有站号相邻两个站号之间用一个空格隔开。

输出格式 Output Format；

只有一行。如果无法乘巴士从饭店到达S公园，则输出
“NO”，否则输出你的程序所找到的最少换车次数，换车次数为0表示不需换车即可到达?

样例输入：

1
2
3
4
3 7
6 7
4 7 3 6
2 1 3 5

样例输出：

1
2

思路：

这道题主要考察输入格式和建图能力，只要在线路里的每一个车站都连上，（有向图）然后求一遍最短路即可，由于体重要求的是换乘的次数，所以在dis[n]的基础上需要再减1。因为刚坐上的车不需要“换”。
建图

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#define INF 99999999
#define MAXN 2020
using namespace std;

struct edge
{
	int y, v, next;
}e[MAXN];
int lin[MAXN];
int len=0;
int n=0, m=0;
int dis[MAXN];
bool vis[MAXN];

inline int Read()
{
	int Num=0, F=1; char ch=getchar();
	while (!isdigit(ch))  {  if (ch == '-') F=-1; ch=getchar();}
	while ( isdigit(ch))  {  Num=(Num<<1)+(Num<<3)+ch-'0'; ch=getchar();}
	return Num*F;
}

inline void insert(int xx, int yy, int vv)
{
	e[++len].next=lin[xx];  lin[xx]=len;
	e[len].v = vv; e[len].y = yy;
}

inline int num(char ch) {
	return ch-'0';
}

void init()
{
	m=Read(); n=Read();
	int q[1000];
	memset(q, 0, sizeof(q));
	for (int i=1;i<=m;++i)
	{
		int a, b=0;
		char p=1;
		while (p!= 10)//注意一下如何读入一行数字直到换行。
		{
			++b;
			scanf("%d", &q[b]);
			p = getchar();
		}
		for (int j=1;j<=b;j++)
		for (int k=j+1;k<=b;k++)
		if (j != k && q[j]!=0)
			insert(q[j],q[k],1);
		memset(q, 0, sizeof(q));
	}
}

void SPFA()//最近学习了一下spfa算法，其实这道题的数据范围floyed都可以过
{
	queue<int> q;
	for (int i=1; i<=n;++i)
	{
		dis[i]=INF;
		vis[i]=0;
	}
	q.push(1); vis[1]=1; dis[1]=0;
	while (!q.empty())
	{
		int u=q.front();
		q.pop(); vis[u]=0;
		for (int i=lin[u]; i; i=e[i].next)
		{
			int v = e[i].y;
			if (dis [v] > dis[u] + e[i].v)
			{
				dis [v] = dis[u] + e[i].v;
				if (vis[v] == 0)
				{
					q.push(v);
					vis[v] = 1;
				}
			}
		}
	}
}

int main()
{
	init();
	SPFA();
	if (dis[n] < INF)
	printf("%d", dis[n]-1);
	else 
	printf("NO");
	return 0;
}