Submission #474769

#	Time	Username	Problem	Language	Result	Execution time	Memory
474769		nguot	Robot (JOI21_ho_t4)	C++14	100 / 100	1069 ms	87792 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fori(x,a,b) for(int x=a;x<=b;x++)
#define ford(x,a,b) for(int x=a;x>=b;x--)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define getbit(x,i) ((x>>i)&1)
#define batbit(x,i) (x|(1ll<<i))
#define tatbit(x,i) (x&~(1<<i))
#define gg exit(0)
#define int long long

const int N = 1e5+10;
map<int,int> f2[N],d[N];
int f1[N],n,m;
struct edge
{
    int to,c,w;
};

map<int,vector<edge> > ke[N];

main()
{
    fasty;
    //freopen("task.inp","r",stdin);
    cin>>n>>m;
    fori(i,1,m)
    {
        int u,v,w,c;
        cin>>u>>v>>c>>w;
        d[u][c]+=w;
        d[v][c]+=w;
        ke[u][c].pb({v,c,w});
        ke[v][c].pb({u,c,w});
    }

    memset(f1,0x3f,sizeof(f1));
    f1[1] = 0;
    priority_queue<pair<int,ii> > h;
	h.push({0,{1,0}});
    //f2[umin][c] : (di vao u = c hoac di ra u cung = c)
    while(!h.empty())
    {
        int dmin,umin,c;
        tie(umin,c) = h.top().se;
        dmin = -h.top().fi;
        h.pop();
        if(c)
        {
            if(f2[umin][c]!=dmin) continue;
            forv(v,ke[umin][c])
            {
                if(f1[v.to] > dmin + d[umin][c] - v.w)
                {
                    f1[v.to] = dmin + d[umin][c] - v.w;
                    h.push({-f1[v.to],{v.to,0}});
                }
            }
        }
        else
        {
            if(f1[umin]!=dmin) continue;
            forv(i,ke[umin]) forv(j,i.se)
            {
                if(f1[j.to] > dmin + d[umin][j.c] - j.w)
                {
                    f1[j.to] = dmin + d[umin][j.c] - j.w;
                    h.push({-f1[j.to],{j.to,0}});
                }
                if(f1[j.to] > dmin + j.w)
                {
                    f1[j.to] = dmin + j.w;
                    h.push({-f1[j.to],{j.to,0}});
                }
                if(!f2[j.to].count(j.c) || (f2[j.to][j.c] > dmin))
                {
                    f2[j.to][j.c] = dmin;
                    h.push({-f2[j.to][j.c],{j.to,j.c}});
                }
            }
        }
    }
    cout<<(f1[n]==f1[0] ? -1 : f1[n]);
}

Compilation message (stderr)

Main.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main()
      | ^~~~

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