Submission #764934

#	Time	Username	Problem	Language	Result	Execution time	Memory
764934		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	157 ms	14488 KiB

commuter_pass

/**
 *    author:  pablo777
 *    created: 26.01.2023 11:04:14
**/
#include <bits/stdc++.h>
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
	//       11111111        \\
	//      11 0  0 11       \\
	//      11  __  11       \\
	//       11111111        \\
	//         1111          \\
	//          ||           \\
	//   aaaaaaaaaaaaaaaa    \\
	//   aaabbbbbbbbbbaaa    \\
	//   aaa  bbbbbb  aaa    \\
	//   aaa  bbbbbb  aaa    \\
	//        |||\\\         \\
	//       |||  \\\        \\
	//      |||    \\\       \\
	//    ####      ####     \\
//        _Abdurrashid_
using namespace std;
typedef pair < ll , ll > pll;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const int N = 1e5 + 7;
ll dst[N];
ll l[N];
vector < pair < int , int > > g[N];
void roma() {
	int n,m;
	cin >> n >> m;
	int q,w,u,v;
	cin >> q >> w >> u >> v;
	for (int i = 1; i <= n; i++) {
        if (i != q) dst[i] = inf;
	}
    for (int i = 1; i <= m; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        g[a].pb({b, c});
        g[b].pb({a, c});
    }
    set < pair < ll, int > > s;
    s.insert({0,q});
    while (s.size()) {
        int v = (*s.begin()).ss;
        s.erase(s.begin());
        for (int i = 0; i < g[v].size(); i++) {
            int to = g[v][i].ff;
            if (dst[to] > dst[v] + g[v][i].ss) {
                dst[to] = dst[v] + g[v][i].ss;
                s.insert({dst[to], to});
                l[to] = v;
            }
        }
    }
    if (dst[w] != inf) {
        int i = w;
        vector < int > h;
        h.pb(w);
        while (i != q) {
            h.pb(l[i]);
            i = l[i];
        }
        for (int i = 0; i < h.size() - 1; i++) {
            int v = h[i];
            for (int j = 0; j < g[v].size(); j++) {
                if (g[v][j].ff == h[i + 1]) {
                    g[v][j].ss = 0;
                }
            }
            v = h[i + 1];
            for (int j = 0; j < g[v].size(); j++) {
                if (g[v][j].ff == h[i]) {
                    g[v][j].ss = 0;
                }
            }
        }
    }
    s.insert({0,u});
    while (s.size()) {
        int v = (*s.begin()).ss;
        s.erase(s.begin());
        for (int i = 0; i < g[v].size(); i++) {
            int to = g[v][i].ff;
            if (dst[to] > dst[v] + g[v][i].ss) {
                dst[to] = dst[v] + g[v][i].ss;
                s.insert({dst[to], to});
                l[to] = v;
            }
        }
    }
    cout << dst[v];
}
//15 5
//1 15
//1 3
//10 15 5
//3 15 1
//4 3 1
//1 10 1
//1 4 4
int main () {
	ios_base::sync_with_stdio (false);
	cin.tie (NULL);
	cout.tie (nullptr);
//	freopen("r.in","r",stdin);
//	freopen("w.out","w",stdout);
	int king = 1,y = 0;
//  cin >> king;
	while (--king+1) {
		y++;
		roma();
	}
	return 0;
}

Compilation message (stderr)

commuter_pass.cpp:11:2: warning: multi-line comment [-Wcomment]
   11 |  //       11111111        \\
      |  ^
commuter_pass.cpp: In function 'void roma()':
commuter_pass.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for (int i = 0; i < g[v].size(); i++) {
      |                         ~~^~~~~~~~~~~~~
commuter_pass.cpp:70:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int i = 0; i < h.size() - 1; i++) {
      |                         ~~^~~~~~~~~~~~~~
commuter_pass.cpp:72:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for (int j = 0; j < g[v].size(); j++) {
      |                             ~~^~~~~~~~~~~~~
commuter_pass.cpp:78:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for (int j = 0; j < g[v].size(); j++) {
      |                             ~~^~~~~~~~~~~~~
commuter_pass.cpp:89:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int i = 0; i < g[v].size(); i++) {
      |                         ~~^~~~~~~~~~~~~

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