#include<bits/stdc++.h>
//12 48
using namespace std;
#define int long long
#define INF 1e17
typedef pair<int, int> ii;
template <typename T>
using vv = vector<vector<T> >;
struct edge{
int u, v, c;
};
int n, k, m;
vector<int> h;
vv<int> g;
vector<edge> e;
vector<vector<int> > dh;
void dijkstra1(int val){ //val is the index of the impp array
int source = h[val];
dh[val] = vector<int>(n, INF);
priority_queue<ii> q;
q.push({0, source});
while(!q.empty()){
pair<int, int> t = q.top();
q.pop();
if(dh[val][t.second] != INF){
assert(dh[val][t.second] <= -t.first);
continue;
}
dh[val][t.second] = -t.first;
for(int eid: g[t.second]){
int next = e[eid].u + e[eid].v - t.second;
if(dh[val][next] == INF){
q.push({t.first - e[eid].c, next});
}else{
assert(dh[val][next] <= (-t.first + e[eid].c));
}
}
}
}
vector<vector<vector<int> > > dab;
signed main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>k>>m;
h.resize(k);
for(int i = 0; i < k; i++){
cin>>h[i]; h[i]--;
}
g.resize(n);
for(int i = 0; i < m; i++){
int a, b, c; cin>>a>>b>>c;
a--, b--;
e.push_back({a, b, c});
g[a].push_back(i);
g[b].push_back(i);
}
//find shortest path from all important to all others
dh.resize(k);
for(int i = 0; i < k; i++){
dijkstra1(i);
}
//d[a][b][i] short distance from i to a and i to b
dab = vector<vector<vector<int> > > (k, vector<vector<int> > (k, vector<int>(n, INF)));
for(int a = 0; a < k; a++){
for(int b = 0; b < k; b++){
if(a == b){
dab[a][a] = dh[a];
}else{
for(int i = 0; i < n; i++){
dab[a][b][i] = dh[a][i] + dh[b][i];
}
}
}
}
//do multisource dijkstra from
for(int a = 0; a < k; a++){
for(int b = a+1; b < k; b++){
//make dab[a][b][i] the best value for i
vector<int> vis(n, 0);
priority_queue<ii> q;
for(int i = 0; i < n; i++){
q.push({-dab[a][b][i], i});
}
while(!q.empty()){
ii t = q.top(); q.pop();
if(vis[t.second]) {
assert(-t.first >= dab[a][b][t.second]);
continue;
}
vis[t.second] = 1;
assert(dab[a][b][t.second] >= -t.first);
dab[a][b][t.second] = -t.first;
for(int eid: g[t.second]){
int next = e[eid].u + e[eid].v - t.second;
if(dab[a][b][next] > (-t.first + e[eid].c)){
q.push({t.first - e[eid].c, next});
assert(vis[next] == 0);
}
}
}
}
}
int bestAns = LONG_LONG_MAX;
//find answer
if(k < 5){
for(int i = 0; i < n; i++){
vector<int> perm(k);
for(int j = 0; j < k; j++) perm[j] = j;
do{
int curAns = 0;
for(int j = 0; j < k; j += 2){
if(j == k-1){
curAns += dab[perm[j]][perm[j]][i];
}else{
int fir = perm[j], sec = perm[j+1];
if(fir > sec) swap(fir, sec);
curAns += dab[fir][sec][i];
}
}
bestAns = min(bestAns, curAns);
}while(next_permutation(perm.begin(), perm.end()));
}
}else{
for(int c = 0; c < 5; c++){
int f1 = c==0?1:0;
for(int f2 = 0; f2 < 5; f2++){
if(f2 == f1 || f2 == c) continue;
int o1 = -1, o2 = -1;
for(o1 = 0; o1 < 5; o1++) if(o1 != f1 && o1 != f2 && o1 != c) break;
o2 = 10 - c + f1 + f2 + o1;
for(int i = 0; i < n; i++){
assert(f1 < f2); assert(o1 < o2);
bestAns = min(bestAns, dab[c][c][i] + dab[f1][f2][i] + dab[o1][o2][i]);
}
}
}
}
cout<<bestAns<<endl;
} #include<bits/stdc++.h>
//12 48
using namespace std;
#define int long long
#define INF 1e17
typedef pair<int, int> ii;
template <typename T>
using vv = vector<vector<T> >;
struct edge{
int u, v, c;
};
int n, k, m;
vector<int> h;
vv<int> g;
vector<edge> e;
vector<vector<int> > dh;
void dijkstra1(int val){ //val is the index of the impp array
int source = h[val];
dh[val] = vector<int>(n, INF);
priority_queue<ii> q;
q.push({0, source});
while(!q.empty()){
pair<int, int> t = q.top();
q.pop();
if(dh[val][t.second] != INF){
assert(dh[val][t.second] <= -t.first);
continue;
}
dh[val][t.second] = -t.first;
for(int eid: g[t.second]){
int next = e[eid].u + e[eid].v - t.second;
if(dh[val][next] == INF){
q.push({t.first - e[eid].c, next});
}else{
assert(dh[val][next] <= (-t.first + e[eid].c));
}
}
}
}
vector<vector<vector<int> > > dab;
signed main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>k>>m;
h.resize(k);
for(int i = 0; i < k; i++){
cin>>h[i]; h[i]--;
}
g.resize(n);
for(int i = 0; i < m; i++){
int a, b, c; cin>>a>>b>>c;
a--, b--;
e.push_back({a, b, c});
g[a].push_back(i);
g[b].push_back(i);
}
//find shortest path from all important to all others
dh.resize(k);
for(int i = 0; i < k; i++){
dijkstra1(i);
}
//d[a][b][i] short distance from i to a and i to b
dab = vector<vector<vector<int> > > (k, vector<vector<int> > (k, vector<int>(n, INF)));
for(int a = 0; a < k; a++){
for(int b = 0; b < k; b++){
if(a == b){
dab[a][a] = dh[a];
}else{
for(int i = 0; i < n; i++){
dab[a][b][i] = dh[a][i] + dh[b][i];
}
}
}
}
//do multisource dijkstra from
for(int a = 0; a < k; a++){
for(int b = a+1; b < k; b++){
//make dab[a][b][i] the best value for i
vector<int> vis(n, 0);
priority_queue<ii> q;
for(int i = 0; i < n; i++){
q.push({-dab[a][b][i], i});
}
while(!q.empty()){
ii t = q.top(); q.pop();
if(vis[t.second]) {
assert(-t.first >= dab[a][b][t.second]);
continue;
}
vis[t.second] = 1;
assert(dab[a][b][t.second] >= -t.first);
dab[a][b][t.second] = -t.first;
for(int eid: g[t.second]){
int next = e[eid].u + e[eid].v - t.second;
if(dab[a][b][next] > (-t.first + e[eid].c)){
q.push({t.first - e[eid].c, next});
assert(vis[next] == 0);
}
}
}
}
}
int bestAns = LONG_LONG_MAX;
//find answer
if(k < 5){
for(int i = 0; i < n; i++){
vector<int> perm(k);
for(int j = 0; j < k; j++) perm[j] = j;
do{
int curAns = 0;
for(int j = 0; j < k; j += 2){
if(j == k-1){
curAns += dab[perm[j]][perm[j]][i];
}else{
int fir = perm[j], sec = perm[j+1];
if(fir > sec) swap(fir, sec);
curAns += dab[fir][sec][i];
}
}
bestAns = min(bestAns, curAns);
}while(next_permutation(perm.begin(), perm.end()));
}
}else{
for(int c = 0; c < 5; c++){
int f1 = c==0?1:0;
for(int f2 = 0; f2 < 5; f2++){
if(f2 == f1 || f2 == c) continue;
int o1 = -1, o2 = -1;
for(o1 = 0; o1 < 5; o1++) if(o1 != f1 && o1 != f2 && o1 != c) break;
o2 = 10 - c + f1 + f2 + o1;
for(int i = 0; i < n; i++){
assert(f1 < f2); assert(o1 < o2);
bestAns = min(bestAns, dab[c][c][i] + dab[f1][f2][i] + dab[o1][o2][i]);
}
}
}
}
cout<<bestAns<<endl;
}
Compilation message
cities.cpp:154:3: error: stray '#' in program
} #include<bits/stdc++.h>
^
cities.cpp:154:4: error: 'include' does not name a type
} #include<bits/stdc++.h>
^~~~~~~
cities.cpp:164:8: error: redefinition of 'struct edge'
struct edge{
^~~~
cities.cpp:11:8: note: previous definition of 'struct edge'
struct edge{
^~~~
cities.cpp:168:5: error: redefinition of 'long long int n'
int n, k, m;
^
cities.cpp:15:5: note: 'long long int n' previously declared here
int n, k, m;
^
cities.cpp:168:8: error: redefinition of 'long long int k'
int n, k, m;
^
cities.cpp:15:8: note: 'long long int k' previously declared here
int n, k, m;
^
cities.cpp:168:11: error: redefinition of 'long long int m'
int n, k, m;
^
cities.cpp:15:11: note: 'long long int m' previously declared here
int n, k, m;
^
cities.cpp:169:13: error: redefinition of 'std::vector<long long int> h'
vector<int> h;
^
cities.cpp:16:13: note: 'std::vector<long long int> h' previously declared here
vector<int> h;
^
cities.cpp:170:9: error: redefinition of 'vv<long long int> g'
vv<int> g;
^
cities.cpp:17:9: note: 'vv<long long int> g' previously declared here
vv<int> g;
^
cities.cpp:171:14: error: redefinition of 'std::vector<edge> e'
vector<edge> e;
^
cities.cpp:18:14: note: 'std::vector<edge> e' previously declared here
vector<edge> e;
^
cities.cpp:172:22: error: redefinition of 'std::vector<std::vector<long long int>, std::allocator<std::vector<long long int> > > dh'
vector<vector<int> > dh;
^~
cities.cpp:19:22: note: 'std::vector<std::vector<long long int>, std::allocator<std::vector<long long int> > > dh' previously declared here
vector<vector<int> > dh;
^~
cities.cpp: In function 'void dijkstra1(long long int)':
cities.cpp:173:6: error: redefinition of 'void dijkstra1(long long int)'
void dijkstra1(int val){ //val is the index of the impp array
^~~~~~~~~
cities.cpp:20:6: note: 'void dijkstra1(long long int)' previously defined here
void dijkstra1(int val){ //val is the index of the impp array
^~~~~~~~~
cities.cpp: At global scope:
cities.cpp:197:31: error: redefinition of 'std::vector<std::vector<std::vector<long long int>, std::allocator<std::vector<long long int> > > > dab'
vector<vector<vector<int> > > dab;
^~~
cities.cpp:44:31: note: 'std::vector<std::vector<std::vector<long long int>, std::allocator<std::vector<long long int> > > > dab' previously declared here
vector<vector<vector<int> > > dab;
^~~
cities.cpp: In function 'int main()':
cities.cpp:199:8: error: redefinition of 'int main()'
signed main(){
^~~~
cities.cpp:46:8: note: 'int main()' previously defined here
signed main(){
^~~~
