题解 P3116 【[USACO15JAN]约会时间Meeting Time】
shadowice1984
2017-09-22 13:07:43
本蒟蒻觉得好像不用拓扑吧。。。
才疏学浅。。。
下面分析下思路；
设d（i，j）为是否存在长为j的路径通向i点；
那么显然
如果d（i，j）是存在的
并且存在由i通向k的道路，那么d（k，cost[i]【k】+j）也是存在的（cost[i][k]是由i到k的路径长）；
所以跑个循环，把所有点遍历，就可以得到通向i的所有长度，（采用权值1）；
再报一遍，就可以得到采用权值2的所有长度；
两个集合取交，再取最小值就好了。
上代码~
```cpp
#include<stdio.h>
using namespace std;
int n;int m;int map1[100][100];int map2[100][100];//邻接矩阵存图
bool d1[100][7000];bool d2[100][7000];
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
map1[i][j]=-1;map2[i][j]=-1;//初始化
}
}
for(int i=0;i<m;i++)
{
int u;int v;int a;int b;
scanf("%d%d%d%d",&u,&v,&a,&b);
map1[u-1][v-1]=a;map2[u-1][v-1]=b;
}
d1[0][0]=true;d2[0][0]=true;//设置边界条件
for(int i=0;i<n;i++)//遍历所有点
{
for(int j=0;j<7000;j++)//合理瞎蒙，到终点不太可能突破7000
{
if(d1[i][j]==true)//这样的路径是否存在
{
for(int k=0;k<n;k++)
{
if(map1[i][k]!=-1)//通向下一个点道路是否存在
{
d1[k][j+map1[i][k]]=true;//更新
}
}
}
}
}
for(int i=0;i<n;i++)//再跑一遍权值2
{
for(int j=0;j<7000;j++)
{
if(d2[i][j]==true)
{
for(int k=0;k<n;k++)
{
if(map2[i][k]!=-1)
{
d2[k][j+map2[i][k]]=true;
}
}
}
}
}
int res=-1;
for(int i=0;i<7000;i++)//从0开始，这样第一个交集元素就是最小元素
{
if(d1[n-1][i]&&d2[n-1][i])
{
res=i;break;
}
}
if(res==-1)
{
printf("IMPOSSIBLE");
}
else
{
printf("%d",res);
}
return 0;//拜拜程序~
}
```