dijkstra

Author Avatar
Xzhah 9月 03, 2019
  • 在其它设备中阅读本文章

#

dijkstra

总结一下dijkstr算法的理解

问题:

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

Input Specification:

Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (≤500) - the number of cities (and the cities are numbered from 0 to N−1), M - the number of roads, C1 and C2 - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1, c2 and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1 to C2.

Output Specification:

For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

Sample Input:

1
2
3
4
5
6
7
8
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

Sample Output:

1
2 4

就是路径最短问题

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
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;
int n,m,c1,c2,t1,t2,l;
long long inf=999999999;
long long w[505]={0},travel[505][505]={inf},dis[505]={inf},num[505]={0},weight[505]={0};
bool s[505]={false};
int main(){
	/*ifstream cinFile("p.in");
	ofstream coutFile("p.out");
	streambuf* CinBuf=cin.rdbuf();
	streambuf* CoutBuf=cout.rdbuf();
	cin.rdbuf(cinFile.rdbuf());
	cout.rdbuf(coutFile.rdbuf());*/
	cin>>n>>m>>c1>>c2;
	fill(travel[0],travel[0]+505*505,inf);//travel记录两点之间的路径距离，如果两点不通则是inf
	fill(dis,dis+505,inf);//还需要记住，fill填充二维数组是从travel[0]开始，也可以是&travel[0][0]
	for(int i=0;i<n;++i){
		cin>>w[i]; //w数组是点值，也就是消防队数量
	}
	for(int i=0;i<m;++i){
		cin>>t1>>t2>>l;
		travel[t1][t2]=travel[t2][t1]=l;

	}
	dis[c1]=0;//dis数组记录到该顶点的最短路径
	num[c1]=1;//num数组记录到该顶点的最短路径条数
	//s[c1]=true;
	weight[c1]=w[c1];
	for(int i=0;i<n;++i){ //每次取一个距离源点最近的点，做完路径距离遍历过后加入s数组(已确定最短距离顶点数组)
		int min=inf;
		int u=-1;
		for(int j=0;j<n;++j){
			if(s[j]==false && dis[j]<min){
				u=j;
				min=dis[j];
			}
		}
		if(u==-1)
			break;
		s[u]=true;
		for(int j=0;j<n;++j){
			if(s[j]==false && travel[u][j]!=inf){//遍历所有与该顶点相连的，未加入s数组的顶点
			if(dis[u]+travel[u][j]<dis[j]){//如果从u点到j点的距离小于目前最短路径，那么替换
				weight[j]=weight[u]+w[j];
				num[j]=num[u];
				dis[j]=dis[u]+travel[u][j];
			}
			else if(dis[u]+travel[u][j]==dis[j]){
				num[j]=num[j]+num[u];//如果距离相同，那么最短路径条数=到u的最短条数和目前方法到j的最短条数
				if(weight[u]+w[j]>weight[j]){
					weight[j]=weight[u]+w[j];//输出点权值最大的最短路径
				}
			}
            }
			}

	}
	cout<<num[c2]<<' '<<weight[c2]<<endl;
	return 0;
}

prim算法

和这个比较像的是prim最小生成树

Problem Description

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。

Output

对每个测试用例，在1行里输出最小的公路总长度。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0

Sample Output

1
2
3
5
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
#include<iostream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;
typedef long long ll;
int t1,t2,l;
ll N,M;
ll maxx=999999999,sum;
ll travel[501][501],dis[501];
bool s[501]={false};
int u;
int main(){
	while(true){
	cin>>N;//>>M;
	if(N==0)
		break;
	M=N*(N-1)/2;
	fill(&travel[0][0],&travel[0][0]+501*501,maxx);
	fill(dis,dis+501,maxx);
	memset(s,false,501);
	sum=0;
	for(int j=0;j<M;++j){
		cin>>t1>>t2>>l;
		travel[t1][t2]=travel[t2][t1]=l;//输入边权值
	}
	dis[t1]=0;//随机选择t1作为起点
	for(int j=1;j<=N;++j){
		u=-1;
		int minn=maxx;
	for(int i=1;i<=N;++i)
	{
		if(s[i]==false && dis[i]<minn)
		{minn=dis[i];
		u=i;
		}
	}
	if(u == -1){
		break;
	}
	s[u]=true;
	sum+=dis[u];
	for(int i=1;i<=N;++i){
		if(s[i]==false && travel[u][i]!=maxx && travel[u][i]<dis[i]){//和dijkstra不一样的地方，如果从u到i可以更近，便舍弃从原点到i,不计算重复路径长度
			dis[i]=travel[u][i];
		}
	}
	}
	cout<<sum<<endl;}
	return 0;
}