Acdream 1083 人民城管爱人民

很好的dp题目，不过当时比赛的时候太傻逼，都没意识到这是dp题。

以后要养成习惯了，对于一个DAG来说，dp是解决相关问题的很好的工具。

对于一个点u，我们记录它的两种状态dp[u][0]表示从u开始没有破坏路的最短路径，dp[u][1]表示从u开始破坏了一条路径的最短路径。

第一个状态的转移很好解决。

第二个状态的转移一定要注意这是一个博弈的过程，城管也是很有智商的。。。

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define inf 10000000

struct edge
{
    int to;
    int cost;
};

const int maxn = 1e4;

vector<edge> g[maxn];
bool vis[maxn];
int dp[maxn][2];
int n,m;

void dfs(int s)
{
    if(vis[s]==true)  return;
    if(s==n-1)
    {
        dp[s][0]=dp[s][1]=0;
        return;
    }
    if(g[s].size()==0)
    {
        dp[s][0]=dp[s][1]=inf;
        return;
    }
    int size=(int)g[s].size();
    vis[s]=true;
    for(int i=0;i<size;i++)
    {
        dfs(g[s][i].to);
    }
    int loc=-1;
    dp[s][0]=inf;
    for(int i=0;i<size;i++)
    {
        edge tmp=g[s][i];
        if(dp[tmp.to][0]+tmp.cost<dp[s][0])
        {
            loc=i;
            dp[s][0]=dp[tmp.to][0]+tmp.cost;
        }
    }
    if(size==1)
    {
        dp[s][1]=inf;
    }
    else
    {
        dp[s][1]=inf;
        int v1=inf,v2=inf;
        for(int i=0;i<size;i++)
        {
            edge tmp=g[s][i];
            v1=min(v1,dp[tmp.to][1]+tmp.cost);
            if(i!=loc)
            {
                v2=min(v2,dp[tmp.to][0]+tmp.cost);
            }
        }
        dp[s][1]=max(v1,v2);
    }
    return;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)  g[i].clear();
        int from,to,cost;
        while(m--)
        {
            scanf("%d%d%d",&from,&to,&cost);
            g[from].push_back((edge){to,cost});
        }
        memset(vis,false,sizeof(vis));
        dfs(0);
        /*
         for(int i=0;i<n;i++)
         {
         printf("%d %d\n",dp[i][0],dp[i][1]);
         }*/
        if(dp[0][1]>=inf)  puts("-1");
        else  printf("%d\n",dp[0][1]);
    }
    return 0;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：Acdream 1083 人民城管爱人民，转载请注明来源！