제출 #834093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
834093		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	245 ms	19392 KiB

commuter_pass

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

const ll INF = 1e18; 
ll D[100005]; 
ll D2[100005]; 
ll prevv[100005];
ll visited[100005]; 
ll tempp[100005]; 
vector<pair<ll, ll>> jalur[100005]; 

void priorityQueue(int jumlahKota, ll D[], ll start, ll prevv[])
{
	for(int i = 1; i <= jumlahKota; i++)
	{
    	D[i] = INF;	
    	visited[i] = 0; 
	}
    D[start] = 0;
    priority_queue<pair<ll, ll>,vector<pair<ll, ll>>,greater<pair<ll, ll>>> q;
    q.push({0,start});
    while(!q.empty())
    {
        pair<ll, ll> p = q.top();
        q.pop();
 
        ll u = p.second, dist = p.first;
//        if(dist > D[u]) continue;
        if(visited[u] == 1)continue; 
        visited[u] = 1; 
        for(pair<ll, ll> pr : jalur[u])
        {
//        	cout << pr.first << " " << pr.second << endl; 
            ll v = pr.first;
            ll next_dist = dist + pr.second;
 
            if(next_dist < D[v])
            {
                D[v] = next_dist;
                q.push({next_dist,v});
                prevv[v] = u; 
            }
        }
    }
}

int main()
{
	int jumlahKota, jumlahJalan, ibuMrit, ibuRat, asal, tujuan; 
	cin >> jumlahKota >> jumlahJalan; 
	cin >> ibuMrit >> ibuRat; 
	cin >> asal >> tujuan; 
	
	for(int i = 0; i < jumlahKota; i++)
	{
		D2[i] = 0; 
		D[i] = 0; 
		prevv[i] = -1; 
	}
	for(int i = 0; i < jumlahJalan; i++)
	{
		ll a, b, c; 
		cin >> a >> b >> c; 
		jalur[a].pb({b, c}); 
		jalur[b].pb({a, c}); 
	}

	priorityQueue(jumlahKota, D2, asal, tempp); 
	ll absres = D2[tujuan]; 

	cout << absres << endl;
	
	return 0;
}

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