【BZOJ3890】[Usaco2015 Jan]Meeting Time

2015.08.17 20:06 Mon | 34次阅读 | 旧日oi | 固定链接 | 源码

Description

给出一个n个点m条边的有向无环图,每条边两个边权。
n<=100,没有重边。
然后要求两条长度相同且尽量短的路径,
路径1采用第一种边权,路径2采用第二种边权。
没有则输出”IMPOSSIBLE”

题解

拓扑+dp,SB题。看代码啥都懂了。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define N 105
struct edge{
    int to,next,v[2];
}e[N*N/2];
int h[N],tp;
void ae(int u,int v,int w1,int w2)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    e[tp].v[0]=w1;e[tp].v[1]=w2;
    h[u]=tp;
}
int n,m,dep[105],ind[N];
bool dp[105][10005][2];
queue<int> q;
int main()
{
    cin>>n>>m;
    for(int u,v,w1,w2,i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&u,&v,&w1,&w2);
        ae(u,v,w1,w2);ind[v]++;
    }
    for(int i=1;i<=n;i++) 
    if(!ind[i]) q.push(i);
    dp[1][0][0]=dp[1][0][1]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v,i=h[u];e[i].to;i=e[i].next)
        {
            ind[v=e[i].to]--;
            dep[v]=max(dep[v],dep[u]+1);
            if(!ind[v]) q.push(v);
            for(int j=0;j<=dep[u]*100;j++)
            {
                if(dp[u][j][0]) dp[v][j+e[i].v[0]][0]=1;
                if(dp[u][j][1]) dp[v][j+e[i].v[1]][1]=1;
            }
        }
    }
    for(int i=0;i<=10000;i++) 
    if(dp[n][i][0]&&dp[n][i][1])
    {
        cout<<i<<endl;
        return 0;
    }
    puts("IMPOSSIBLE");
}```