Submission #58739004

---

Source Code Expand

#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef pair<ll,ll> pll;
#define double long double
const double eps = 1e-9; 
#define FOR(i,a,b) for(long long i=a;i<b;i++)
#define all(v) v.begin(),v.end()
template <typename I>
void print(vector<I> &v){
    FOR(i,0,v.size()){cout << v[i] << " ";}
    cout << "\n";
}
ll gcd(ll a,ll b){
    if(a==0){return b;}
    else if(b==0){return a;}
    else if(a<b){return gcd(b%a,a);}
    else{return gcd(a%b,b);}
}
ll lcm(ll a,ll b){
    return (a/gcd(a,b))*b;
}
void setIO(string name = "") {
    freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
    freopen((name + ".out").c_str(), "w", stdout);
}
const ll MOD1 = (1e9+7);
const ll MOD2 = (998244353);
const ll MOD3 = (805306457);
const ll MOD4 = (402653189);
void solve(){
    // store very big numbers may mean log
    ll n,m;
    cin >> n >> m;
    vll a(m);
    vll b(m);
    vll c(m);
    vector<vector<pll>> adj(n);
    FOR(i,0,m){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--,b[i]--;
        adj[a[i]].push_back({b[i],c[i]});
        adj[b[i]].push_back({a[i],c[i]});
    }
    // cout << "hello" << "\n";
    vll cnt1_a(n,0);
    vll cnt1_b(n,0);
    vll cnt1_c(n,0);
    vll cnt1_d(n,0);
    vll cnt2_a(n,0);
    vll cnt2_b(n,0);
    vll cnt2_c(n,0);
    vll cnt2_d(n,0);
    vll d1(n,9e13);
    vll d2(n,9e13);
    d1[0] = 0;
    cnt1_a[0] = 1;
    cnt1_b[0] = 1;
    cnt1_c[0] = 1;
    cnt1_d[0] = 1;
    priority_queue<pll,vector<pll>,greater<pll>> pq;
    pq.push({0,0});
    vector<bool> visited(n,false);
    while(!pq.empty()){
        ll curr = pq.top().second;
        pq.pop();
        if(visited[curr]) continue;
        visited[curr] = true;
        for(pll i:adj[curr]){
            if(visited[i.first]) continue;
            ll alt = d1[curr]+i.second;
            if(alt<d1[i.first]){
                d1[i.first] = alt;
                pq.push({alt,i.first});
                cnt1_a[i.first] = cnt1_a[curr];
                cnt1_b[i.first] = cnt1_b[curr];
                cnt1_c[i.first] = cnt1_c[curr];
                cnt1_d[i.first] = cnt1_d[curr];
            }
            else if(alt==d1[i.first]){
                cnt1_a[i.first] = (cnt1_a[curr]+cnt1_a[i.first])%MOD1;
                cnt1_b[i.first] = (cnt1_b[curr]+cnt1_b[i.first])%MOD2;
                cnt1_c[i.first] = (cnt1_c[curr]+cnt1_c[i.first])%MOD3;
                cnt1_d[i.first] = (cnt1_d[curr]+cnt1_d[i.first])%MOD4;
            }
        }
    }
    d2[n-1] = 0;
    cnt2_a[n-1] = 1;
    cnt2_b[n-1] = 1;
    cnt2_c[n-1] = 1;
    cnt2_d[n-1] = 1;
    pq.push({0,n-1});
    visited.assign(n,false);
    while(!pq.empty()){
        ll curr = pq.top().second;
        pq.pop();
        if(visited[curr]) continue;
        visited[curr] = true;
        for(pll i:adj[curr]){
            if(visited[i.first]) continue;
            ll alt = d2[curr]+i.second;
            if(alt<d2[i.first]){
                d2[i.first] = alt;
                pq.push({alt,i.first});
                cnt2_a[i.first] = cnt2_a[curr];
                cnt2_b[i.first] = cnt2_b[curr];
                cnt2_c[i.first] = cnt2_c[curr];
                cnt2_d[i.first] = cnt2_d[curr];
            }
            else if(alt==d2[i.first]){
                cnt2_a[i.first] = (cnt2_a[i.first]+cnt2_a[curr])%MOD1;
                cnt2_b[i.first] = (cnt2_b[i.first]+cnt2_b[curr])%MOD2;
                cnt2_c[i.first] = (cnt2_c[i.first]+cnt2_c[curr])%MOD3;
                cnt2_d[i.first] = (cnt2_d[i.first]+cnt2_d[curr])%MOD4;
            }
        }
    }
    // print(d1);
    // print(d2);
    FOR(i,0,m){
        bool poss = false;
        ll curr = d1[a[i]]+d2[b[i]]+c[i];
        if(curr==d1[n-1]){
            ll ways1 = (cnt1_a[a[i]]*cnt2_a[b[i]])%MOD1;
            ll ways2 = (cnt1_b[a[i]]*cnt2_b[b[i]])%MOD2;
            ll ways3 = (cnt1_c[a[i]]*cnt2_c[b[i]])%MOD3;
            ll ways4 = (cnt1_d[a[i]]*cnt2_d[b[i]])%MOD4;
            if(ways1==cnt1_a[n-1]&&ways2==cnt1_b[n-1]&&ways3==cnt1_c[n-1]&&ways4==cnt1_d[n-1]){
                poss = true;
            }
        }
        curr = d1[b[i]]+d2[a[i]]+c[i];
        if(curr==d1[n-1]){
            ll ways1 = (cnt1_a[b[i]]*cnt2_a[a[i]])%MOD1;
            ll ways2 = (cnt1_b[b[i]]*cnt2_b[a[i]])%MOD2;
            ll ways3 = (cnt1_c[b[i]]*cnt2_c[a[i]])%MOD3;
            ll ways4 = (cnt1_d[b[i]]*cnt2_d[a[i]])%MOD4;
            if(ways1==cnt1_a[n-1]&&ways2==cnt1_b[n-1]&&ways3==cnt1_c[n-1]&&ways4==cnt1_d[n-1]){
                poss = true;
            }
        }
        if(poss){
            cout << "Yes" << "\n";
        }
        else{
            cout << "No" << "\n";
        }
    }
}

signed main(){
    //setIO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void setIO(std::string)’:
Main.cpp:40:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |     freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:41:12: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   41 |     freopen((name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Judge Result