Submission #1312518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312518		galactic_programmer	Robot (JOI21_ho_t4)	C++20	0 / 100	81 ms	7928 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],one[N],two[N],more[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,curr_col=e.col;
        for(auto f:one[x])
        {
            int y=f.x,col=f.col,cost=f.cost;
            if(d[y]>d[x])
            {
                d[y]=d[x];
                q.push({y,col,d[y]});
            }
        }
        for(auto f:two[x])
        {
            int y=f.x,col=f.col,cost=f.cost;
            if(curr_col==col) cost=0;
            if(d[y]>d[x]+cost)
            {
                d[y]=d[x]+cost;
                q.push({y,col,d[y]});
            }
        }
        for(auto f:more[x])
        {
            int y=f.x,col=f.col,cost=f.cost;
            if(d[y]>d[x]+cost)
            {
                d[y]=d[x]+cost;
                q.push({y,col,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) one[i].push_back({x,col,cost});
            else if(f[col].x==2) two[i].push_back({x,col,cost});
            else more[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