Submission #1155730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155730		dnnnda	Robot (JOI21_ho_t4)	C++20	0 / 100	148 ms	17264 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define ll long long
//#define int long long
//#pragma GCC optimize("Ofast, unroll-loop")
//#pragma GCC target("avx,avx2")
#pragma GCC optimize("O3")
const int inf=0x3f3f3f3f;
const ll inff=0x3f3f3f3f3f3f3f3f;
const int X=1000000007;

vector<array<int,3>> adj[100005];
vector<int> cs[100005];
ll len[100005];
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;

bool ch(int u, int co){
    auto iter=lower_bound(cs[u].begin(),cs[u].end(),co);
    iter++;
    if(iter!=cs[u].end()&&*iter==co) return 1;
    return 0;
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    memset(len,0x3f,sizeof len);
    int n, m; cin >> n >> m;
    for(int i=1 ; i<=m ; i++){
        int a, b, c, p; cin >> a >> b >> c >> p;
        adj[a].push_back({b,c,p});
        adj[b].push_back({a,c,p});
        cs[a].push_back(c);
        cs[b].push_back(c);
    }
    for(int i=1 ; i<=n ; i++) sort(cs[i].begin(),cs[i].end());
    len[1]=0;
    pq.push({0,1});
    while(!pq.empty()){
        auto[l,u]=pq.top();
        pq.pop();
        if(len[u]<l) continue;
        for(auto[v,c,p]:adj[u]){
            if(l+p*ch(u,c)<len[v]){
                len[v]=l+p*ch(u,c);
                pq.push({len[v],v});
            }
        }
    }
    cout << (len[n]==inff ? -1LL : len[n]) << '\n';

    return 0;
}

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42