题解 P3116 【[USACO15JAN]约会时间Meeting Time】

本蒟蒻觉得好像不用拓扑吧。。。

才疏学浅。。。

下面分析下思路；

设d（i，j）为是否存在长为j的路径通向i点；

那么显然

如果d（i，j）是存在的

并且存在由i通向k的道路，那么d（k，cost[i]【k】+j）也是存在的（cost[i][k]是由i到k的路径长）；

所以跑个循环，把所有点遍历，就可以得到通向i的所有长度，（采用权值1）；

再报一遍，就可以得到采用权值2的所有长度；

两个集合取交，再取最小值就好了。

上代码~

#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;//拜拜程序~
}