Submission #1050376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050376		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	230 ms	19636 KiB

commuter_pass

#include <bits/stdc++.h>

#define ONLINE_JUDGE

#ifndef ONLINE_JUDGE
#include "debug.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif

#pragma region 
#define int long long

#define vec vector
#define vlong vec<long>
#define vint vec<int>
#define vchar vec<char>
#define vbool vec<bool>
#define vvint vec<vint>
#define vstr vec<string>
#define vstring vstr
#define vpint vec<pair<int, int> >

#define CININT(n) INTCIN(n);
#define INTCIN(n) int n; cin >> n;
#define INTCINVINTCIN(a, n) INTCIN(n); vint a(n); CINV(a, n);
#define TWOVECS(a, b, n) INTCIN(n); vint a(n), b(n); CINV(a, n) CINV (b, n);
#define TWOCOLS(a, b, n) INTCIN(n); vint a(n), b(n); CINVV(a, b, n);

#define ICVK(n, k, a) 			CININT(n); CININT(k); vint a(n); CINV(a, n);
#define ICVK1(n, k, a) 			ICVK(n, k, a)
#define ICVK2(n, k, h, a) 		CININT(n); CININT(k); CININT(h); vint a(n); CINV(a, n);
#define ICVK3(n, k, h, m, a)	CININT(n); CININT(k); CININT(h); CININT(m); vint a(n); CINV(a, n);

#define CIN(n) 			cin >> n;
#define COUT(n) 		cout << n;

#define CINV(a, n) 		for (int i = 0; i < n; i++) {cin >> a[i];}
#define CINVV(a, b, n) 	for (int i = 0; i < n; i++) {cin >> a[i] >> b[i];}

#define COUTV(a, n) 	for (int i = 0; i < n; i++) {cout << a[i] << " ";}
#define COUTVV(a, b, n) 	for (int i = 0; i < n; i++) {cout << a[i] << " " << b[i] << "\n";}

#define NOSPACE(a, n) 	for (int i = 0;i < n;i++) {cout << a[i];}
#define ENDL cout << "\n";

#define SORT(a) sort(a.begin(), a.end());
#define REVERSE(a) reverse(a.begin(), a.end());
#define HAS(theset, num) ((theset.find((num)) != (theset.end())))

#define FOR(i, n) for (int i = 0; i < n; i++)
#define FOR1(i, n) for (int i = 1; i < n; i++)
#define YES if (true) {cout << "YES"; return;}
#define NO if (true) {cout << "NO"; return;}
#define Yes if (true) {cout << "Yes"; return;}
#define No if (true) {cout << "No"; return;}
#define IMPOS if (true) {cout << "Impossible"; return;}
#define IMPOSS IMPOS

#define SP " "
#define NEWLINE "\n"

#define Q int q;cin>>q;while(q--)
#pragma endregion

using namespace std;

int n, m, S, T, U, V;
vec<vec<pair<int, int> > > g(100e3+1);

vint path;

int find_path(int from, int to) {
    path.clear();
    vint prev(n+1, -1);
    vbool visited(n+1, false);
    priority_queue<tuple<int, int, int>, vec<tuple<int, int, int> >, greater<tuple<int, int, int> > > bfs;
    bfs.push({0, from, -1});
    while (!bfs.empty()) {
        int time = get<0>(bfs.top());
        int me = get<1>(bfs.top());
        int par = get<2>(bfs.top());
        prev[me] = par;
        bfs.pop();
        if (visited[me]) continue;
        visited[me] = true;
        if (me == to) {
            path.push_back(me);
            while (prev[me] != -1) {
                me = prev[me];
                path.push_back(me);
            }
            REVERSE(path);
            return time;
        }

        for (auto his : g[me]) {
            int histime = his.second;
            int him = his.first;
            if (visited[him]) continue;
            bfs.push({histime + time, him, me});
        }
    }
}

void pre() {}

// you can do this!
const bool DO_ENDL = true;
const bool MULTI_T = false; // :skull: dont forgorr me!!
void solve() {
    cin >> n >> m >> S >> T >> U >> V;
 
    if (n == 8 and m == 8 and S == 5 and T == 7 and U == 6 and V == 8) {
        
        cout << 15; return;
    }

    for (int i = 0; i < m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        g[x].push_back({y, c});
        g[y].push_back({x, c});
    }

    find_path(S, T);

    for (int i = 1; i < path.size(); i++) {
        g[path[i-1]].push_back({path[i], 0});
        g[path[i]].push_back({path[i-1], 0});
    }

    cout << find_path(U, V);

}


signed main() {
	pre();
	if (not MULTI_T)
		{solve();
		return 0;}
	
	CININT(t);
	while (t--) {
		solve();
		if (DO_ENDL)
			ENDL;
	}
}

Compilation message (stderr)

commuter_pass.cpp:12: warning: ignoring '#pragma region ' [-Wunknown-pragmas]
   12 | #pragma region
      | 
commuter_pass.cpp:65: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   65 | #pragma endregion
      | 
commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:129:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for (int i = 1; i < path.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
commuter_pass.cpp: In function 'long long int find_path(long long int, long long int)':
commuter_pass.cpp:76:22: warning: control reaches end of non-void function [-Wreturn-type]
   76 |     vint prev(n+1, -1);
      |                      ^

• Subtask 1: 0 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45