제출 #1312517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312517		galactic_programmer	Robot (JOI21_ho_t4)	C++20	0 / 100	64 ms	7636 KiB

Main

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N=1e5+5;
const int inf=1e18;
struct freq
{
    int x,time;
};
struct elem
{
    int x,col,cost;
    bool operator<(const elem& e) const
    {
        return cost<e.cost;
    }
};
freq f[N];
int n,m,i,j,x,y,c,p,d[N];
vector<elem> edge[N],uniq[N],multiple[N];
void dijkstra(int orig)
{
    for(i=1;i<=n;++i)
        d[i]=inf;
    priority_queue<elem> q;
    q.push({orig,0,0});
    d[orig]=0;
    while(!q.empty())
    {
        auto e=q.top();
        q.pop();
        int x=e.x;
        //cout<<d[2]<<endl;
        for(auto f:uniq[x])
        {
            int y=f.x;
            if(d[y]>d[x])
            {
                d[y]=d[x];
                q.push({y,0,d[y]});
            }
        }
        for(auto f:multiple[x])
        {
            int y=f.x,cost=f.cost;
            if(d[y]>d[x]+cost)
            {
                d[y]=d[x]+cost;
                q.push({y,0,d[y]});
            }
        }
    }
}
signed main()
{
    cin>>n>>m;
    for(i=1;i<=m;++i)
    {
        cin>>x>>y>>c>>p;
        edge[x].push_back({y,c,p});
    }
    for(i=1;i<=n;++i)
    {
        for(auto e:edge[i])
        {
            int x=e.x,c=e.col;
            if(f[c].time!=i)
            {
                f[c].time=i;
                f[c].x=1;
            }
            else
                f[c].x++;
        }
        for(auto e:edge[i])
        {
            int x=e.x,col=e.col,cost=e.cost;
            if(f[col].x==1) uniq[i].push_back({x,col,cost});
            else multiple[i].push_back({x,col,cost});
        }
    }
    dijkstra(1);
    if(d[n]==inf) cout<<-1;
    else cout<<d[n];
    return 0;
}

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