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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
#include<iostream>
#include<queue>
#include<vector>
#include<set>
using namespace std;
struct node {
int v, len;
node(int _v, int _len) {
v = _v;
len = _len;
}
};
int N, M, S, D, INF = 1000000000;
int teams[500], d[500], countInq[500];
vector<node> graph[500];
bool inq[500];
set<int> pre[500];
vector<int> tempPath, path;
int count = 0, maxTeams = 0;
bool spfa(int s);
void dfs(int nowVisit);
int main() {
std::ios::sync_with_stdio(false);
cin >> N >> M >> S >> D;
for(int i = 0; i < N; i++) {
cin >> teams[i];
}
for(int i = 0; i < M; i++) {
int v1, v2, len;
cin >> v1 >> v2 >> len;
graph[v1].push_back(node(v2, len));
graph[v2].push_back(node(v1, len));
}
spfa(S);
dfs(D);
cout << count << " " << maxTeams << endl;
for(int i = path.size() - 1; i >= 0; i--){
cout << path[i];
if(i == 0){
cout << endl;
}else{
cout << " ";
}
}
return 0;
}
bool spfa(int s) {
fill(d, d + N, INF);
fill(countInq, countInq + N, 0);
fill(inq, inq + N, false);
d[s] = 0;
queue<int> q;
q.push(s);
countInq[s]++;
inq[s] = true;
while(!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for(int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i].v;
int len = graph[u][i].len;
if(d[u] + len < d[v]) {
d[v] = d[u] + len;
pre[v].clear();
pre[v].insert(u);
if(!inq[v]) {
q.push(v);
inq[v] = true;
countInq[v]++;
if(countInq[v] > N - 1){
return false;
}
}
}else if(d[u] + len == d[v]) {
pre[v].insert(u);
if(!inq[v]) {
q.push(v);
inq[v] = true;
countInq[v]++;
if(countInq[v] > N - 1){
return false;
}
}
}
}
}
return true;
}
void dfs(int nowVisit) {
tempPath.push_back(nowVisit);
if(nowVisit == S){
count++;
int tempTeams = 0;
for(int i = 0; i < tempPath.size(); i++){
tempTeams += teams[tempPath[i]];
}
if(tempTeams > maxTeams){
maxTeams = tempTeams;
path = tempPath;
}
tempPath.pop_back();
return;
}
for(set<int>::iterator it = pre[nowVisit].begin(); it != pre[nowVisit].end(); it++){
dfs(*it);
}
tempPath.pop_back();
}
|
