【Henu ACM Round#14 F】 President and Roads

在这里输入题意

【题解】

处理出起点到任意点的最短路以及最短路条数=>dis[0][i],cnt[0][i]
然后
把所有的边反向
处理出在反图上终点到任意点的最短路以及最短路条数=>dis[1][i],cnt[1][i]
dis数组的初值为-1,表示无穷大
设起点到终点的最短路为mini
起点到终点的最短路条数为minicnt
对于每一条边(x,y,z)
如果dis[0][x]==-1 || dis[1][y]==-1代表x或者y不能到达起点或终点
则直接输出NO
否则
如果dis[0][x]+dis[1][y]==mini 且 cnt[0][x]*cnt[1][y]==minicnt的话
输出YES.这条边肯定在最短路上
(这种情况是把重边也考虑进去了的,因为如果有重边那么minicnt肯定不等于cnt[0][x]*cnt[1][y],肯定还要乘上重边的个数的
否则
让z减小到满足dis[0][x]+dis[1][y]+z求最短路条数要用dijkstra算法

用spfa会错

这道题某个点卡1e9+7模数

改成987654321就对了

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e5;

const ll MOD = 987654321;

int n,m,s,t;

ll cnt[2][N+10];

ll dis[2][N+10];

vector<pair<int,int> > g[2][N+10];

pair<int,pair<int,int> > bian[N+10];

queue<int> dl;

map<pair<int,pair<int,int> >,int>dic;

void get_dis(int s,int k){

    for (int i = 1;i <= n;i++) dis[k][i] = -1;

    cnt[k][s] = 1;

    dis[k][s] = 0;

    priority_queue<pair<ll,int> ,vector<pair<ll,int> >,greater<pair<ll,int> > > pq;

    pq.push(make_pair(0,s));

    while (!pq.empty()){

        auto temp1 = pq.top();

        pq.pop();

        int x = temp1.second;ll dis0 = temp1.first;

        if (dis[k][x]!=dis0) continue;

        for (auto temp:g[k][x]){

            int y = temp.first;ll z = temp.second;

            if (dis[k][y]==-1 || dis[k][y]>dis0+z){

                dis[k][y] = dis0 + z;

                cnt[k][y] = cnt[k][x];

                pq.push({dis[k][y],y});

            }else if (dis[k][y]==dis0+z) cnt[k][y]=(cnt[k][y]+cnt[k][x])%MOD;

        }

    }

}

int main()

{

    #ifdef LOCAL_DEFINE

        freopen("rush.txt","r",stdin);

    #endif // LOCAL_DEFINE

    ios::sync_with_stdio(0),cin.tie(0);

    cin >> n >> m >>s>>t;

    for (int i = 1;i <= m;i++){

        int x,y,z;

        cin >> x >> y >>z;

        dic[{x,{y,z}}]++;

        bian[i] = {x,{y,z}};

        g[0][x].push_back({y,z});

        g[1][y].push_back({x,z});

    }

    get_dis(s,0);

    get_dis(t,1);

    for (int i = 1;i <= m;i++){

        int x,y;

        x = bian[i].first;y = bian[i].second.first;

        if (dis[0][x]<0 || dis[1][y]<0) {

            cout<<"NO"<<endl;

            continue;

        }

        ll z = bian[i].second.second;

        if (dis[0][x]+dis[1][y]+z==dis[0][t] && (cnt[0][x]*cnt[1][y]%MOD)==cnt[0][t]){

                cout<<"YES"<<endl;

        }else{

            ll need = dis[0][x]+dis[1][y]+z-dis[0][t]+1;

            if ((z-need)>=1){

                cout<<"CAN "<<need<<endl;

            }else{

                cout<<"NO"<<endl;

            }

        }

    }

    return 0;

}

巴特西

【Henu ACM Round#14 F】 President and Roads

最新文章

热门文章