제출 #9226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
9226		kkjjkk	Your life (kriii2_Y)	C++98	4 / 4	96 ms	10876 KiB

Y

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<queue>
#include<deque>
using namespace std;

const int MAX_V = 200005;
const int INF = 987654321;

int V;
vector<pair<int, int> > adj[MAX_V];

vector<int> dijkstra(int src) {
	vector<int> dist(V, INF);
	dist[src] = 0;
	priority_queue<pair<int, int> > pq;
	pq.push(make_pair(0, src));
	while(!pq.empty()) {
		int cost = -pq.top().first;
		int here = pq.top().second;
		pq.pop();
		if(dist[here] < cost) continue;
		for(int i = 0; i < adj[here].size(); ++i) {
			int there = adj[here][i].first;
			int nextDist = cost + adj[here][i].second;
			if(dist[there] > nextDist) {
				dist[there] = nextDist;
				pq.push(make_pair(-nextDist, there));
			}
		}
	}
	if(dist[V - 1] == INF) printf("-1");
	else printf("%d", dist[V - 1]);
	return dist;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    V = n + 1;
    for(int i = 0; i < m; i++) {
         int a, b;
         scanf("%d %d", &a, &b);
         adj[a].push_back(make_pair(b, 1));
    }
    dijkstra(1);
}

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3