제출 #59022

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
59022	2018-07-20 08:27:36	tmwilliamlin168	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	678 ms	21356 KiB

commuter_pass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pli pair<ll, int>
#define fi first
#define se second
const int mxN=1e5;
int n, m, s, t, u, v;
vector<pli> adj[mxN];
ll du[mxN], dv[mxN], ds[mxN], dt[mxN], dp[mxN], ans;
priority_queue<pli, vector<pli>, greater<pli>> pq;
void dijkstra(int s, ll dist[mxN]) {
  memset(dist, 0x3F, 8*n);
  dist[s]=0;
  pq.push({0, s});
  while(!pq.empty()) {
    pli p=pq.top();
    pq.pop();
    int u=p.se;
    if(p.fi>dist[u])
      continue;
    for(pli e : adj[u]) {
      int v=e.se;
      if(dist[u]+e.fi<dist[v]) {
        dist[v]=dist[u]+e.fi;
        pq.push({dist[v], v});
      }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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