Submission #643175

#	Time	Username	Problem	Language	Result	Execution time	Memory
643175		karrigan	Robot (JOI21_ho_t4)	C++14	0 / 100	139 ms	28200 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long mx=1e18;
const int maxn=2e5+9;
int u[maxn];
int v[maxn];
int c[maxn];
long long p[maxn];
vector<int>fake[100001];
struct lena{
int v;
long long w;
bool operator < (const lena &p)const{
return w>p.w;
}
};
vector<lena>a[100001];
int cnt[maxn];
long long b[100001];
int use[100001];
priority_queue<lena>cc;
void sp(int u){
b[u]=0;
cc.push({u,0});
while (!cc.empty()){
    auto temp=cc.top();
    cc.pop();
    if (use[temp.v]==1)continue;
    use[temp.v]=1;
    for (auto v:a[temp.v]){
        if (b[v.v]>b[temp.v]+v.w){
            b[v.v]=b[temp.v]+v.w;
            cc.push({v.v,b[v.v]});
        }
    }
}
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>c[i]>>p[i];
        fake[u[i]].push_back(i);
        fake[v[i]].push_back(i);
    }
    for (int i=1;i<=n;i++){
        for (auto v1:fake[i]){
            cnt[c[v1]]++;
        }
        for (auto v1:fake[i]){
            if (cnt[c[v1]]==1){
                if (u[v1]!=i)a[i].push_back({u[v1],0});
                else a[i].push_back({v[v1],0});
            }
            else {
                if (u[v1]!=i)a[i].push_back({u[v1],p[v1]});
                else a[i].push_back({v[v1],p[v1]});
            }
        }
        for (auto v1:fake[i]){
            cnt[c[v1]]=0;
        }
    }
    for (int i=1;i<=n;i++){
        b[i]=1e18;
	}
	sp(1);
	if (b[n]==mx)cout<<-1;
	else cout<<b[n];

}

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