Submission #43294

ソースコード

?
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
// - YDK - {{{
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <sstream>
#include <numeric>
#include <string>
#include <cstdio>
#include <vector>
#include <tuple>
#include <cmath>
#include <queue>
#include <regex>
#include <set>
#include <map>
using namespace std;
#define eb emplace_back
#define emp emplace
#define fi first
#define se second
#define debug(...) fprintf(stderr, __VA_ARGS__ )
#define outl(x) out < (x) < '\n'
#define outl2(x,y) out < (x) < ' ' < (y) < '\n'
#define endl '\n'
#define rep(i,n) for(int i=0; i<(int)(n); ++i)
#define ALL(x) x.begin(), x.end()
#define yesno(f,y,n)puts((f)? (#y):(#n))
#define ODD(n) ((n)&1)
#define EVEN(n) (!ODD(n))
#define LEN(obj) ((obj).size())
#define NIL(n) (!~(n))
#define _ ' '
#define $ '\n'
#define _NAMESPACE_YDK_ namespace ydk {
#define _END_NAMESPACE_ }
template<class A, class B>inline bool chmax(A &a, B b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, B b){return b<a ? a=b,1 : 0;}
template<class T>using MaxHeap = priority_queue< T, vector<T>, greater<T> >;
using ll = long long;
using pii = pair<int, int>;
using byte= unsigned char;
inline bool inside(int x, int y, int W, int H) { return x>=0 && y>=0 && x<W && y<H; }
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int dx[] = {1, 0, -1, 0};
constexpr int dy[] = {0, 1, 0, -1};
struct Point: public pii {
int &x = this->first, &y = this->second;
explicit Point(int x=0, int y=0): pii(x, y) {}
};
struct Writer
{
static constexpr size_t BUFF_SIZE = 1 << 18;
static char _buf[BUFF_SIZE];
explicit Writer() { setvbuf(stdout, _buf, _IOFBF, sizeof(_buf)); }
inline void ln() {putchar('\n');}
inline Writer& operator() (int n) {printf("%d", n); return *this;}
inline Writer& operator() (ll n) {printf("%lld", n); return *this;}
inline Writer& operator() (char c) {printf("%c", c); return *this;}
inline Writer& operator() (double d){printf("%lf", d); return *this;}
inline Writer& operator() (const char* s){printf("%s", s); return *this;}
inline Writer& operator() (const string &s){printf("%s", s.c_str()); return *this;}
inline Writer& operator() (bool f) {printf("%s", f?"true":"false"); return *this;}
inline Writer& operator() (void) {putchar('\n'); return *this;}
template<class InputIterator>
inline Writer& operator() (InputIterator first, InputIterator last, const char *space=" ")
{
for(; first != last; ++first) {
(*this)(*first);
printf("%s", (first+1 == last)? "\n" : space);
}
return *this;
}
};
char Writer::_buf[BUFF_SIZE];
template<class T> inline Writer& operator < (Writer &o, const T &v) { return o(v); }
struct Scanner
{
char tmp[65536];
inline Scanner& read(int &n) {scanf("%d", &n); return *this;}
inline Scanner& read(ll &n) {scanf("%lld", &n); return *this;}
inline Scanner& read(char &c) {scanf(" %c", &c); return *this;}
inline Scanner& read(double &d) {scanf("%lf", &d); return *this;}
inline Scanner& read(char *s) {scanf("%s", s); return *this;}
inline Scanner& read(string &s) {scanf("%s",tmp); s=string(tmp); return*this;}
};
template<class T> inline Scanner& operator > (Scanner &in, T &v) { return in.read(v); }
template<class T> inline Scanner& operator , (Scanner &in, T &v) { return in.read(v); }
Writer out;
Scanner in;
// }}}
_NAMESPACE_YDK_
constexpr int LIM = (int)1e5 * 2;
int V, E;
vector<pii> G[LIM];
int mcos[LIM];
void dijkstra(int s)
{
MaxHeap<pii> pq;
pq.emp(0, s);
memset(mcos, INF, sizeof(mcos));
mcos[s] = 0;
while( !pq.empty() ) {
auto u = pq.top(); pq.pop();
if (mcos[u.se] < u.fi) continue;
for (auto e : G[u.se]) {
int nxt = e.se;
int nc = u.fi + e.fi;
if (chmin(mcos[nxt], nc)) {
pq.emp(nc, nxt);
}
}
}
return;
}
signed main(void)
{
in> V, E;
rep(i, E) {
int s, t, c;
in> s, t, c;
G[s].eb(c, t);
G[t].eb(c, s);
}
dijkstra(1);
if (mcos[V] == INF) outl("NA");
else outl(mcos[V]);
return 0;
}
_END_NAMESPACE_
signed main(void) { return ydk::main(); }

ステータス

項目 データ
問題 0431 - 君も始めようダイクストラ大好き厨
ユーザー名 Arumakan_ei1727
投稿日時 2018-09-15 12:55:16
言語 C++17
状態 Accepted
得点 1
ソースコード長 4668 Byte
最大実行時間 72 ms
最大メモリ使用量 9568 KB

セット

セット 得点 Cases
1 ALL 1 / 1 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
m_in1.txt AC 72 ms 9568 KB
1
r_in1.txt AC 31 ms 6800 KB
1
r_in2.txt AC 31 ms 6896 KB
1
r_in3.txt AC 35 ms 6840 KB
1
r_in4.txt AC 30 ms 6580 KB
1
r_in5.txt AC 34 ms 7208 KB
1
r_in6.txt AC 35 ms 7120 KB
1
r_in7.txt AC 26 ms 6440 KB
1
r_in8.txt AC 34 ms 6552 KB
1
r_in9.txt AC 33 ms 7264 KB
1
r_in10.txt AC 24 ms 6224 KB
1
r_in11.txt AC 29 ms 6708 KB
1
r_in12.txt AC 40 ms 6844 KB
1
r_in13.txt AC 30 ms 6816 KB
1
r_in14.txt AC 33 ms 6844 KB
1
r_in15.txt AC 28 ms 6840 KB
1
r_in16.txt AC 34 ms 6416 KB
1
r_in17.txt AC 29 ms 6520 KB
1
r_in18.txt AC 32 ms 6584 KB
1
r_in19.txt AC 31 ms 6340 KB
1
r_in20.txt AC 27 ms 6648 KB
1
r_in21.txt AC 31 ms 6132 KB
1
r_in22.txt AC 22 ms 6304 KB
1
r_in23.txt AC 33 ms 6392 KB
1
r_in24.txt AC 25 ms 6416 KB
1
r_in25.txt AC 33 ms 6512 KB
1
r_in26.txt AC 33 ms 6656 KB
1
r_in27.txt AC 31 ms 6692 KB
1
r_in28.txt AC 31 ms 6584 KB
1
r_in29.txt AC 31 ms 6680 KB
1
r_in30.txt AC 31 ms 6828 KB
1