Submission #824569

#	Time	Username	Problem	Language	Result	Execution time	Memory
824569		trangtranha28	Robot (JOI21_ho_t4)	C++14	100 / 100	567 ms	72300 KiB

Main

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

const int MAXN = 1e5 + 2;

int n, m;

bool check[MAXN] = {false};
int val[MAXN] = {0};

vector <pair <int, pair <int, int> > > vt[MAXN];
unordered_map <int, int> ump[MAXN];
map <int, int> mp[MAXN];

void Dijkstra() {
	priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > pq;
    pq.push(make_pair(0, 0));
    
    while(pq.empty() == false) {
        pair <int, int> u = pq.top();
        pq.pop();
        
        if(check[u.second] == true) {
        	continue;
		} else {
			check[u.second] = true;
		}
        
        val[u.second] = u.first;
        for(int i = 0; i < (int)(vt[u.second].size()); i++) {
        	pair <int, pair <int, int> > x = vt[u.second][i];
            if(mp[x.first].find(x.second.first) == mp[x.first].end()) {
            	mp[x.first][x.second.first] = u.first;
			}
			
            int temp = u.first;
            map <int, int> :: iterator it = mp[u.second].find(x.second.first);
            if(it != mp[u.second].end()) {
            	temp = it->second;
			}
            pq.push(make_pair(min(temp + ump[u.second][x.second.first] - x.second.second, u.first + x.second.second), x.first));
        }
    }
    return;
}

void programme() {
	// input:
    cin >> n >> m;
    
    for(int i = 0; i < m; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        
		a--;
		b--;
		
        ump[a][c] += d;
        ump[b][c] += d;
        
        vt[a].push_back({b,{c,d}});
        vt[b].push_back({a,{c,d}});
    }
    
    // solve:
    Dijkstra();
    
    // output:
    if(check[n - 1] == false) {
        printf("-1\n");
    } else {
    	cout << val[n-1] << "\n";
	}
	return;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
//	freopen("_mint.inp", "r", stdin);
//	freopen("_mint.out", "w", stdout);
	
	programme();
    return 0;
}

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