看懂题意就是成功的一半
明显状压DP
dij预处理K之间的最短路
先枚举状态的话就有单调性可以省掉一维了
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> using namespace std; struct node { int x,y,d,next; }a[410000];int len,last[21000]; void ins(int x,int y,int d) { len++; a[len].x=x;a[len].y=y;a[len].d=d; a[len].next=last[x];last[x]=len; } int n,d[21000];bool v[21000]; struct dij { int d,id; dij(){} dij(int D,int ID){d=D,id=ID;} friend bool operator>(dij d1,dij d2){return d1.d>d2.d;} friend bool operator<(dij d1,dij d2){return d1.d<d2.d;} };priority_queue<dij,vector<dij>,greater<dij> >q; int dijkstra(int st,int dis) { memset(d,63,sizeof(d));d[st]=dis; memset(v,false,sizeof(v)); q.push(dij(d[st],st)); while(!q.empty()) { dij tno=q.top();q.pop(); if(v[tno.id]==true)continue; v[tno.id]=true; int x=tno.id; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(d[y]>d[x]+a[k].d) { d[y]=d[x]+a[k].d; q.push(dij(d[y],y)); } } } return d[n]; } int K,mp[30][30],f[30][2100000],cq[30],th[30]; int DP() { memset(f,63,sizeof(f)); for(int i=2;i<=K;i++) { dijkstra(i,0); for(int j=2;j<=K;j++) mp[i][j]=min(mp[i][j],d[j]); th[i]=d[n]; if(cq[i]==0)f[i][1<<i-2]=d[1]; } int maxp=(1<<K-1)-1; for(int zt=0;zt<=maxp;zt++) for(int i=2;i<=K;i++) if(f[i][zt]!=f[0][0]) { for(int j=2;j<=K;j++) { int B=(1<<j-2); if((zt&B)==0&&(zt&cq[j])==cq[j]) f[j][zt^B]=min(f[j][zt^B],f[i][zt]+mp[i][j]); } } int ret=(1<<30); for(int i=2;i<=K;i++) ret=min(ret,f[i][maxp]+th[i]); return ret; } int main() { freopen("a.in","r",stdin); freopen("a.out","w",stdout); int m,x,y,dd; scanf("%d%d%d",&n,&m,&K);K++; len=0;memset(last,0,sizeof(last)); memset(mp,63,sizeof(mp)); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&dd); ins(x,y,dd),ins(y,x,dd); } int U; scanf("%d",&U); memset(cq,0,sizeof(cq)); while(U--) { scanf("%d%d",&x,&y); if(x!=1)cq[y]|=(1<<x-2); } if(K==1) { dijkstra(1,0); printf("%d ",d[n]); } else printf("%d ",DP()); return 0; }