oj.uz

답안 #559657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559657 2022-05-10T11:05:43 Z Garguy22 페리들 (NOI13_ferries) C++17
0 / 40
 469 ms 20484 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
#define pb push_back
#define mp make_pair

const int MAXN = 1e5 + 7;
const int INF = 1e9 + 7;

vector<ll> adj[MAXN], wt[MAXN];
ll dis[MAXN];

int main(){
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int x, y, z;
		cin >> x >> y >> z;
		adj[y].pb(x);
		wt[x].pb(z);
	}
	for(int i = 1; i <= n; i++)
		sort(wt[i].begin(), wt[i].end());
	for(int i = 1; i <= n; i++)
		dis[i] = INF;
	priority_queue<pll , vector<pll>, greater<pll> > q;
	q.push(mp(0, n));
	dis[n] = 0;
	while(!q.empty()){
		pll x = q.top();
		q.pop();
		ll d = x.first, u = x.second;
		if(d <= dis[u]){
			for(auto v : adj[u]){
				ll temp = wt[v].back();
				wt[v].pop_back();
				if(dis[v] > d){
					dis[v] = d + temp;
					q.push(mp(dis[v], v));
				}
			}
		}
	}
	cout << dis[1] << endl;

	return 0;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5008 KB Output is correct
2 Incorrect 5 ms 5020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 6416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 469 ms 20484 KB Output isn't correct
2 Halted 0 ms 0 KB -