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
| #include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define maxn 105 #define put() putchar('\n') #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> using namespace std; void read(int &x){ int f=1;x=0;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();} x*=f; } namespace Debug{ Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;} Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);} Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;} #define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__) }using namespace Debug; #define fi first #define se second #define mk make_pair const int mod=1e9+7; int power(int x,int y=mod-2) { int sum=1; while (y) { if (y&1) sum=sum*x%mod; x=x*x%mod;y>>=1; } return sum; } int h[maxn],head=1; int n,m,k,p[maxn]; struct yyy { int to,z,w; void add(int x,int y,int val) { to=y;z=h[x];h[x]=head;w=val; } }a[2005]; int f[(1<<10)+5][maxn]; queue<int>q; void spfa(int id) { int i,x; while (!q.empty()) { x=q.front();q.pop(); for (i=h[x];i;i=a[i].z) if (f[id][a[i].to]>f[id][x]+a[i].w) { f[id][a[i].to]=f[id][x]+a[i].w; q.push(a[i].to); } } } const int inf=1e9; signed main(void){ int i,x,y,z,s,t; memset(f,0x3f,sizeof(f)); read(n);read(m);read(k); for (i=1;i<=m;i++) { read(x),read(y),read(z); a[++head].add(x,y,z); a[++head].add(y,x,z); } for (i=1;i<=k;i++) read(p[i]),f[1<<i-1][p[i]]=0; int N=(1<<k); for (s=1;s<N;s++) { for (i=1;i<=n;i++) { for (t=s&(s-1);t;t=(t-1)&s) f[s][i]=min(f[s][i],f[t][i]+f[t^s][i]); if (f[s][i]<inf) q.push(i); } spfa(s); } printf("%d",f[N-1][p[1]]); return 0; }
|