题目大意：给定一张拓扑图，每条边有两个边权，求两条1到n的路径，第一条用边权1，，第二条用边权2，要求两条路径长度相等且最短
注意到边权<=100,n<=100，因此一条路径的长度最大只有10000
拓扑序DP一下用bitset做就行了
#include <bitset>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 110using namespace std;struct abcd{int to,next;int f1,f2;}table[5050];int head[M],tot;int n,m,degree[M];bitset<10100> f[M],g[M];void Add(int x,int y,int z1,int z2){degree[y]++;table[++tot].to=y;table[tot].f1=z1;table[tot].f2=z2;table[tot].next=head[x];head[x]=tot;}int main(){int i,x,y,z1,z2;cin>>n>>m;for(i=1;i<=m;i++){scanf("%d%d%d%d",&x,&y,&z1,&z2);Add(x,y,z1,z2);}static int q[M],r,h;f[1][0]=g[1][0]=true;for(i=1;i<=n;i++)if(!degree[i])q[++r]=i;while(r!=h){int x=q[++h];for(i=head[x];i;i=table[i].next){f[table[i].to]|=f[x]<<table[i].f1;g[table[i].to]|=g[x]<<table[i].f2;if(!–degree[table[i].to])q[++r]=table[i].to;}}for(i=0;i<=10000;i++)if(f[n][i]&&g[n][i])return cout<<i<<endl,0;return cout<<"IMPOSSIBLE"<<endl,0;}
用最少的悔恨面对过去
