显然这样的路径一定是选择了与1相邻的不同的两点分别作为起点和终点（除1本身）。如果能将每一组起点终点都计算到就可以得出最优解了。暴力显然不行。注意到我们每次求出的是单源最短路径，考虑如何充分利用信息。那么有一种神奇的方法：按照编号的二进制的某一位给所有与1相邻的点分组，一组作为起点另一组作为终点，然后断掉所有由1到终点的边并跑以1为起点的单源最短路。这样可以得到该情况下的最优答案。并且如果对于每一位都这样操作，注意到任意两点的编号二进制下肯定存在一位不同，那么其一定会在某一次时被分进两组统计入答案。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 5010 #define M 20010 #define inf 700000000 int n,m,p[N],d[N],t=-1,ans=inf; bool flag[N]; struct data{int to,nxt,len; }edge[M]; struct data2 { int x,d; bool operator <(const data2&a) const { return d>a.d; } }; priority_queue<data2> q; void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;} void dijkstra() { while (!q.empty()) q.pop(); memset(d,42,sizeof(d));d[1]=0;q.push((data2){1,0}); memset(flag,0,sizeof(flag)); for (int i=1;i<=n;i++) { while (!q.empty()&&flag[q.top().x]) q.pop(); if (q.empty()) break; data2 v=q.top();q.pop(); flag[v.x]=1; for (int j=p[v.x];~j;j=edge[j].nxt) if (v.d+edge[j].len<d[edge[j].to]) { d[edge[j].to]=v.d+edge[j].len; q.push((data2){edge[j].to,d[edge[j].to]}); } } } void solve(int t,int op) { for (int i=p[1];~i;i=edge[i].nxt) if (op^((edge[i].to&t)>0)) edge[i].len+=inf; dijkstra(); for (int i=p[1];~i;i=edge[i].nxt) if (op^((edge[i].to&t)>0)) edge[i].len-=inf,ans=min(ans,d[edge[i].to]+edge[i^1].len); } int main() { #ifndef ONLINE_JUDGE freopen("bzoj2069.in","r",stdin); freopen("bzoj2069.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(); memset(p,255,sizeof(p)); for (int i=1;i<=m;i++) { int x=read(),y=read(),w=read(),v=read(); addedge(x,y,w),addedge(y,x,v); } t=1; while (t<=n) solve(t,0),solve(t,1),t=t<<1; cout<<ans; return 0; }