以前从来没真正写过SPFA，难怪training的时候做不出来了……大悲剧啊……题目的意思就是说在一个很大很大的图中从一个固定的点开始访问其中一些点并最终回到起点，求最短的路径。一些点的数量不多过10个。很容易想到状态dp。
设dp[i][j]表示的是当前在i点并且已经访问了点的状态为j。转移方程为
dp[i][j]=dp[p][k]+dis[p][i] if( (j^k)==(1<<i) && (1<<p)&(k)==true )
其中j的已访问节点数比k大1。所以做bottom-up的DP，以已访问的节点数来做。
最后最麻烦的就是SPFA的写法，参照百度百科写了一个。效率还不错。
int n,m,s,st[11]; int next[200010],ev[200010],ew[200010],nbs[100005]; int used[100005],q[100005],dis[11][100005]; void spfa(int s,int id) { int head=0,tail=1,u,v,w; for(int i=0;i<n;i++) { used[i]=q[i]=0; dis[id][i]=inf; } dis[id][s]=0; q[tail]=s; used[s]=1; while(head!=tail) { head=(head+1)%(n+1); u=q[head]; used[u]=0; for(int i=nbs[u];i;i=next[i]) { v=ev[i]; w=ew[i]; if(dis[id][v]-w>dis[id][u]) { dis[id][v]=dis[id][u]+w; if(!used[v]) { tail=(tail+1)%(n+1); q[tail]=v; used[v]=1; } } } } } |
要加油了。