差分约束求调
查看原帖
差分约束求调
1049051
JiuZhE66666楼主2024/6/3 13:35
#include<bits/stdc++.h>

#define ll long long
using namespace std;
ll dis[100005];
const ll maxs=2e18;
struct node
{
    ll to,len;
};
vector<node> G[100025];

struct fresh
{
    ll pos,val;
    bool operator<(const fresh &b)const
    {
        return b.val<val;
    }
};
int main()
{
    ll n,m,Q;
    cin>>n>>m>>Q;

    fill(dis,dis+n+5,maxs);
    for(ll i=1;i<=m;i++)
    {
        ll l,r,s;
        cin>>l>>r>>s;

        G[l-1].push_back({r,s});
        G[r].push_back({l-1,-s});
    }

    priority_queue<fresh> q;
    q.push({0,0});

    while(q.size())
    {
        ll now=q.top().pos,val=q.top().val;
        q.pop();
        if(dis[now]<=val)  continue;
        dis[now]=val;

        for(auto next:G[now])
        {
            ll to=next.to,len=next.len;
            if(dis[to]>dis[now]+len)
            {
                q.push({to,dis[now]+len});
            }
        }
    }


    while(Q--)
    {
        ll l,r;
        cin>>l>>r;
        if(dis[l-1]!=maxs&&dis[r]!=maxs) cout<<dis[r]-dis[l-1]<<endl;
        else puts("UNKNOWN");
    }
    return 0;
}

2024/6/3 13:35
加载中...