AT_abc137_e [ABC137E] Coins Respawn 题解

PizzaYY · 2023-07-18 11:07:41 · 题解

思路

其实很简单。

由于最后到达终点要支付 T\times P 枚金币，不妨把这些金币处理到每条边中，即每个边的权值间 P。

然后再跑一遍最长路，如果有环就输出 -1。

接下来判环。

上图就是一个环。红边表示松弛。可以发现，每个点都更新了一次 1 号点。

所以，当一个点更新大于 n 次时就有环。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3+5;
int n,m,k,head[N],cnt,nxt[N],to[N],g[N],dis[N],s[N];
bool vis[N],vs[N];
void add(int x,int y,int z)
{
    nxt[++cnt] = head[x];
    head[x] = cnt;
    to[cnt] = y;
    g[cnt] = z;
}
void bfs()
{
    memset(vs,0,sizeof vs);
    dis[1] = 0;
    queue<int> q;
    q.push(1);
    while(!q.empty())
    {
        int u = q.front();q.pop();
        vs[u] = 0;
        for(int i = head[u];i;i = nxt[i])
        {
            int v = to[i];
            if(dis[v]<dis[u]+g[i]&&vis[v])//不与n联通就没必要松弛了
            {
                dis[v] = dis[u]+g[i];
                if(!vs[v]) q.push(v),s[v]++,vs[v] = 1;
                if(s[v]>n)//判环
                {
                    cout<<-1;
                    exit(0);
                }
            }
        }
    }
}
void dfs(int x,int y)
{
    if(x==n)
    {
        vis[y] = 1;
        return;
    }
    for(int i = head[x];i;i = nxt[i])
        if(!vs[to[i]])
            vs[to[i]] = 1,dfs(to[i],y);
}//判是否与n联通
signed main()
{
    cin>>n>>m>>k;
    memset(dis,128,sizeof dis);
    for(int i = 1,x,y,z;i<=m;i++)
        cin>>x>>y>>z,add(x,y,z-k);
    for(int i = 1;i<=n;i++)
    {
        memset(vs,0,sizeof vs);
        vs[i] = 1;
        dfs(i,i);
    }
    bfs();
    if(dis[n]<0) dis[n] = 0;
    cout<<dis[n];
    return 0;
}