Submission #718066

#	Time	Username	Problem	Language	Result	Execution time	Memory
718066		vinnipuh01	Robot (JOI21_ho_t4)	C++17	0 / 100	498 ms	45284 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <stack>
#include <string>
#include <map>
#include <queue>
#define int long long
#define sqrt sqrtl

using namespace std;

const long long oo = 1e18;

long long sum, ans = 0, mx = 0, mn = 1000000000, num, pos;


/*
    ViHHiPuh

   (( `'-""``""-'` ))
     )-__-_.._-__-(
   / --- (o _ o) --- \
   \ .-* ( .0. ) *-. /
   _'-. ,_ '=' _, .-'_
  / `;#'#'# - #'#'#;` \
 \_)) -----'#'----- ((_/
      # --------- #
  '# ------- ------ #'
  /..-'# ------- #'-.\
  _\...-\'# -- #'/-.../_
  ((____)- '#' -(____))


    cout << fixed << setprecision(6) << x;


    freopen ( "sum.in", "r", stdin )
*/

int n, m, x[ 200001 ], y[ 200001 ], z[ 200001 ], t[ 200001 ];
vector <pair<int, int> > v[ 100001 ];
map <int, int> mp[ 100001 ];
int d[ 100001 ];
set <pair<int, int> > st;

main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for ( int i = 1; i <= m; i ++ ) {
    	cin >> x[ i ] >> y[ i ] >> z[ i ] >> t[ i ];
    	mp[ x[ i ] ][ z[ i ] ] += t[ i ];
    	mp[ y[ i ] ][ z[ i ] ] += t[ i ];
	}
	for ( int i = 1; i <= m; i ++ ) {
		v[ x[ i ] ].push_back( { y[ i ], min( mp[ x[ i ] ][ z[ i ] ] - t[ i ], t[ i ] ) } );
		v[ y[ i ] ].push_back( { x[ i ], min( mp[ y[ i ] ][ z[ i ] ] - t[ i ], t[ i ] ) } );
	}
	for ( int i = 1; i <= n; i ++ )
		d[ i ] = oo;
	d[ 1 ] = 0;
	st.insert( { 0, 1 } );
	while ( st.size() ) {
		int u = st.begin()->second;
		st.erase( st.begin() );
		for ( auto to : v[ u ] ) {
			if ( d[ to.first ] > d[ u ] + to.second ) {
				st.erase( { d[ to.first ], to.first } );
				d[ to.first ] = d[ u ] + to.second;
				st.insert( { d[ to.first ], to.first } );
			}
		}
	}
	if ( d[ n ] == oo )
		cout << "-1";
	else
		cout << d[ n ];
}

/*

h[ i ] + i * 2 < h[ i + 1 ] + i * 2 + 4

h[ i ] - h[ i + 1 ] < 4

3 5 2 4 1
5 9 8 14 13

*/

Compilation message (stderr)

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

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