Submission #2530719

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
#define TO(x,t,f) ((x)?(t):(f))
#define CLR(mat) memset(mat, 0, sizeof(mat))
#define FILV(x,a) fill(x.begin(),x.end(),a)
#define FILA(ar,N,a) fill(ar,ar+N,a)
#define NEXTP(x) next_permutation(x.begin(),x.end())
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define pb push_back
#define pri(aa) cout<<(aa)<<endl
const ll INF=1e9+7;
const ll N = 100002;
int n,m,R;
vector<int> r,ju;
int d[201][201];
int ans=INF;

int nagasa(){
	int ans=0;
	FOR(i,1,R){
		ans+=d[r[ju[i]]][r[ju[i-1]]];
	}
	return ans;
}



int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m>>R;
	FOR(i,0,R)ju.pb(i);
	r.resize(R);
	FOR(i,0,R){
		cin>>r.at(i);
		r[i]--;
	}
	FOR(i,0,201){
		FOR(j,0,201){
			d[i][j]=INF;
		}
	}
	FOR(i,0,m){
		int a,b,c;
		cin>>a>>b>>c;
		a--;b--;
		if(d[a][b]>c){
			d[a][b]=d[b][a]=c;
		}
	}
	FOR(i,0,n){
		FOR(j,0,n){
			FOR(k,0,n){
				if(d[j][k]>d[j][i]+d[i][k])d[j][k]=d[j][i]+d[i][k];
			}
		}
	}
	ans=nagasa();
	do{
		int k=nagasa();
		if(ans>k)ans=k;
	}while(NEXTP(ju));
	pri(ans);
	return 0;
}

Submission Info

Judge Result