Submission #444592

#	Time	Username	Problem	Language	Result	Execution time	Memory
444592		O_o	Robot (JOI21_ho_t4)	C++14	100 / 100	1185 ms	88904 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)

#define pb push_back
#define mp make_pair
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define precise(i) fixed << setprecision(i)
#define fi first
#define se second
#define sz(x) ((int)(x).size())

#define err() cout<<"\n==================================\n";
#define errA(A) for(auto i:A) cout<<i<<" "; cout<<"\n";
#define err1(a) cout<<#a<<" "<<a<<"\n";
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<"\n";
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<"\n";
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<"\n";

const int logN = 20;
const int M = 1000000007;
const int INF = 1e17;
#define PI 3.14159265;
const int N = 200005;

#define Pii pair<int,int>
#define Vi vector<int>
#define Vpii vector<Pii>
#define PQ priority_queue<int>

void setIO(string d_name = "") {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if(sz(d_name)){
		freopen((d_name+".in").c_str(), "r", stdin);
		freopen((d_name+".out").c_str(), "w", stdout);
	}
}

map<int, vector<pair<int, Pii>>> adj[100001];
map<int, int> grp[100001];

int32_t main()
{
    setIO();
    int n, m;
    cin>>n>>m;
    rep(_,0,m)
    {
    	int a, b, c, p;
    	cin>>a>>b>>c>>p;
    	adj[a][c].pb(mp(b, mp(c, p)));
    	adj[b][c].pb(mp(a, mp(c, p)));
    	grp[a][c]+= p;
    	grp[b][c]+= p;
    }
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    Vi dist(100001, INF);
    map<int, int> dp[100001];
    dist[1]= 0;
    pq.push({0, 1, 0});
    while(!pq.empty())
    {
    	int x, c, p;
        tie(p, x, c)= pq.top();
        pq.pop();
        if(c)
        {
            if(p != dp[x][c])
            {
                continue;
            }
            for(auto e: adj[x][c])
            {
                int cost= p+grp[x][c];
                if(cost-e.se.se < dist[e.fi])
                {
                    dist[e.fi]= cost-e.se.se;
                    pq.push({dist[e.fi], e.fi, 0});
                }
            }
        }
        else
        {
            if(p != dist[x])
            {
                continue;
            }
            for(auto e1: adj[x])
            {
                for(auto e2: e1.se)
                {
                    if(dist[e2.fi] > p + e2.se.se)
                    {
                        dist[e2.fi]= p+e2.se.se;
                        pq.push({dist[e2.fi], e2.fi, 0});
                    }
                    if(dist[e2.fi] > p + grp[x][e2.se.fi] - e2.se.se)
                    {
                        dist[e2.fi]= p + grp[x][e2.se.fi] - e2.se.se;
                        pq.push({dist[e2.fi], e2.fi, 0});
                    }
                    if(!dp[e2.fi].count(e2.se.fi) || dp[e2.fi][e2.se.fi] > p)
                    {
                        dp[e2.fi][e2.se.fi]= p;
                        pq.push({dp[e2.fi][e2.se.fi], e2.fi, e2.se.fi});
                    }
                }
            }
        }
    }
    if(dist[n] == INF)
    {
        cout<<"-1";
    }
    else
    {
        cout<<dist[n];
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:40:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   freopen((d_name+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:41:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   freopen((d_name+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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