出门旅行(tour)

提交数: 459, 通过率: 32.68%, 平均分: 49.74

题目描述:

在神奇的 oi 国度，有 n 个城市 m 条双向道路，每条道路连接了两个不同的城市。寒假到了，小 S 决定出门旅游一趟。因为以往跟团旅游多了，这次小 S 决定自驾游。对于自驾游，小 S 最关心的自然是燃油的耗费，为了省钱，小 S 请你帮他找一条最短的路。

输入格式:

第一行两个整数 n,m，表示有 n 个城市和 m 条双向道路。城市从 1..n 编号。
接下来 m 行，每行三个正整数 a,b,c，表示 a 和 b 之间有一条长为 c 的双向道路。a,b 不相同，且 c 不超过 1000
注意：两个城市之间可能会有多条双向道路。
接下来一行两个整数，s,t，表示小 S 本次旅行的出发地和目的地。s,t 不相同。

输出格式:

仅一行一个整数，表示最短的距离。如果不能到达，请输出-1。

样例输入:

3 3
1 2 1
1 3 3
2 3 1
1 3

样例输出:

2

提示:

【样例解释】
1->2->3 即是最优解。
【数据范围】
对于 30%的数据，n<=100,m<=1000
对于 100%的数据，n<=2000,m<=100000

 

图的存储方式：

存储1：
二维数组，注意存储空间

存储2：
struct data{
	int to, val;
};
vector< data > a[100001];

存储3：
struct node{
	int to,val,next;
}edge[ 400001 ];  //边的数量
int num, head[ 20001 ];   //顶点的数量
void add( int u, int v, int w ){
	edge[ ++num ].to = v;
	edge[ num ].val = w;
	edge[ num ].next = head[u];
	head[ u ] = num;
}

存储4：
和存储3原理一样，只是用多个独立的数组存储
int tot, to[ N ], val[ N ], _next[ N ], _head[ N ];
void add( int x, int y, int z ){
	to[ ++tot ] = y;
	val[ tot ] = z;
	_next[ tot ] = _head[x];
	_head[x] = tot;
}
存储3和存储4称为链式前向星，由某个顶点出发的边的顶点构成一条链，链的尾结点指针（next) 为0。
时间限制: 1000ms
空间限制: 128MB

来源: 基础训练1-t4