제출 #1087198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087198		tdkhai	Robot (JOI21_ho_t4)	C++14	100 / 100	429 ms	63476 KiB

Main

/*
K stands for "Khongbietcode"
grade 11 computer science
Tran Dai Nghia Highschool for the gifted
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long
#define pb push_back
#define ull unsigned long long
#define llll pair<ll,ll>
#define llllm map<ll,ll>
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b/gcd(a,b)
#define X first
#define Y second
#define INF 1LL<<62

using namespace std;
using namespace __gnu_pbds;

struct edge
{
    ll v,color,w;
    bool operator > (const edge a) const
    {
        return w>a.w;
    }
};
const ll N=1e5+1;
vector<edge> a[N];
map<ll,ll> sum[N];
map<ll,ll> cnt[N];
ll d[N];
void solve(){
    ll n,m;
    cin >> n >> m;
    for(int i=0;i<m;i++)
    {
        ll u,v,w,c;
        cin >> u >> v >> c >> w;
        a[u].pb({v,c,w});
        a[v].pb({u,c,w});
        sum[u][c]+=w;
        sum[v][c]+=w;
    }
    for(int i=2;i<=n;i++)
    {
        d[i]=INF;
    }
    priority_queue< llll,vector<llll>,greater<llll> > pq;
    pq.push({0,1});
    while(pq.size())
    {
        llll top=pq.top();
        pq.pop();
//        cout << top.Y << '\n';
        if(top.X!=d[top.Y]) continue;
        for(auto i:a[top.Y])
        {
            if(cnt[i.v].find(i.color)==cnt[i.v].end())
            {
                cnt[i.v][i.color]=top.X;
            }
            ll w=top.X;
            auto f=cnt[top.Y].find(i.color);
            if(f!=cnt[top.Y].end())w=f->Y;
//            pq.push({d[top.Y]=min({w+sum[top.Y][i.color]-i.w,top.X+i.Y}),i.v});
            if(d[i.v]>min(d[top.Y]+i.w,w+sum[top.Y][i.color]-i.w))
            {
                pq.push({d[i.v]=min(w+sum[top.Y][i.color]-i.w,d[top.Y]+i.w),i.v});
            }
        }
    }
    if(d[n]>=INF)
    {
        cout << -1;
    }
    else
    {
        cout << d[n];
    }
}
int main(){
    fastIO;
//    freopen("tdk.inp","r",stdin);
//    freopen("tdk.out","w",stdout);
    //freopen("tdk.err","b",stderr);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
        cout << endl;
    }
    // cout << "\n" << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
    return 0;
}

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