a1003

题目大意

根据距离人数构成最短路径,如果距离相等,选择人数多的,最后输出有几条最短路径和最多几个人

解决方法

最短路径的代码正常写法

0.首先初始化

G的所有值设置为maxn,距离d也设置maxn,visited设置false

1.首先是选出距离的点

1
2
3
4
5
6
7
8
9
int less=-1;
int min=maxn;
// 首先找到最小编
for (int i = 0; i < n; ++i) {
if (d[i]<min&&!visited[i]){
less=i;
min=d[i];
}
}

2.异常检查

就是如果没找到最短的边那就结束

1
2
3
if (less==-1){
return 0;
}

3.设置为访问过,并且通过这个点的周围所有点更新d

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
visited[less]= true;
// 通过这个最短点找与他相连的其他点,通过这个桥梁更新距离
for (int j = 0; j < n; ++j) {
if (!visited[j]&&G[less][j]!=maxn){
if (d[less]+G[less][j]<d[j]){
d[j]=d[less]+G[less][j];
ren[j]=cost[j]+ren[less];
times[j]=times[less];
}else if (d[less]+G[less][j]==d[j]){
if (cost[j]+ren[less]>ren[j]){
ren[j]=cost[j]+ren[less];
}
times[j]+=times[less];
//
}
}

}

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <cmath>
#include <set>
#include <stack>
#include <queue>

//cin用多了超市

using namespace std;
const int maxn=100100;

int main() {
int n,m,c1,c2;
cin>>n>>m>>c1>>c2;
int cost[n];
int d[n];
fill(d,d+n,maxn);
bool visited[n];
fill(visited,visited+n, false);
int G[n][n];
fill(G[0],G[0]+n*n,maxn);
int ren[n];
fill(ren,ren+n,0);
for (int i = 0; i < n; ++i) {
cin>>cost[i];
}
for (int j = 0; j < m; ++j) {
int p,q,t;
cin>>p>>q>>t;
G[p][q]=G[q][p]=t;
}
d[c1]=0;
int times[n];
fill(times,times+n,0);
times[c1]=1;
ren[c1]=cost[c1];
for (int k = 0; k < n; ++k) {
// 寻找最短的点
int less=-1;
int min=maxn;
// 首先找到最小编
for (int i = 0; i < n; ++i) {
if (d[i]<min&&!visited[i]){
less=i;
min=d[i];
}
}
// 没找到直接返回
if (less==-1){
return 0;
}
visited[less]= true;
// 通过这个最短点找与他相连的其他点,通过这个桥梁更新距离
for (int j = 0; j < n; ++j) {
if (!visited[j]&&G[less][j]!=maxn){
if (d[less]+G[less][j]<d[j]){
d[j]=d[less]+G[less][j];
ren[j]=cost[j]+ren[less];
times[j]=times[less];
}else if (d[less]+G[less][j]==d[j]){
if (cost[j]+ren[less]>ren[j]){
ren[j]=cost[j]+ren[less];
}
times[j]+=times[less];
//
}
}

}
}

cout<<times[c2]<<" "<<ren[c2];
return 0;
}