Submission #00057

ソースコード

?
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
146
147
148
149
150
151
152
153
154
#include "bits/stdc++.h" // {{{
using namespace std;
#define val const auto
#define eb emplace_back
#define emp emplace
#define fi first
#define se second
#define X first
#define Y second
#define outl(x) cout << (x) << '\n'
#define rep(i,n) for(int i=0; i < (int)(n); ++i)
#define ALL(x) begin(x), end(x)
#define TMPLT(T,U) template<class T, class U>
#define ten(p) ((long long)(1e##p))
#define FILL(a,v) memset((a), (v), sizeof(a))
#define FAST() ios::sync_with_stdio(false), cin.tie(nullptr)
#ifndef DEBUG
#define debug(...)
#define show(x)
#define show2(x,y)
#define LN()
#endif
typedef long long ll;
typedef pair<int,int> pii;
namespace ydk{
TMPLT(T,U) inline bool chmax(T &a, U b){return b>a ? a=b,1 : 0;}
TMPLT(T,U) inline bool chmin(T &a, U b){return b<a ? a=b,1 : 0;}
TMPLT(T,U) inline constexpr common_type_t<T,U> gcd(T x, U y)
{ return (x<y)? gcd(y,x) : (y <= 0)? x : gcd(y, x % y); }
TMPLT(T,U) inline constexpr ll lcm(T x, U y) { return (ll)x/gcd(x,y) * y; }
constexpr int INF = 0x3f3f3f3f;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3fLL;
// }}}
constexpr int MX = ten(4) + 10;
#define COLD 0
#define WARM 1
#define HOT 2
const char *toString_templ(short t)
{
const char *s[] = {"Cold", "Warm", "Hot"};
return s[t];
}
struct P {
int cost, node, rem;
short templ;
explicit P(int c=0, int u=0, short t=0, int r=0)
: cost(c), node(u), templ(t), rem(r) {}
inline bool operator< (const P &p) const { return cost < p.cost; }
inline bool operator> (const P &p) const { return cost > p.cost; }
};
int N, M, X;
vector<pii> G[MX];
int templ[MX];
bool canGoto(const P &now, const short nxtT, int dist)
{
const short nowT = now.templ;
if (nxtT == WARM || nxtT == nowT) {
return true;
}
if ( (nxtT == COLD && nowT == HOT) || (nxtT == HOT && nowT == COLD) ) {
return now.rem - dist <= 0;
}
debug("################################ canGoto: Error ###########################\n");
return false;
}
short getNextTempl(short now, short nxt)
{
if(nxt == WARM) { return now; }
return nxt;
}
int getNextRem(int nowRem, int dist, short nxtT)
{
if(nxtT == WARM) { return max(0, nowRem-dist); }
return X;
}
// mcos[node][templ][rem] := mincost
int mcos[MX][3][205];
void dijkstra(int s)
{
priority_queue<P, vector<P>, greater<P>> pq;
// cost node templ rem
pq.emp(0, s, templ[s], X);
FILL(mcos, INF);
mcos[s][templ[s]][X] = 0;
while(!pq.empty())
{
const P now = pq.top(); pq.pop();
debug("node: %2d, cost: %2d, temp: %4s, rem: %3d\n",
now.node, now.cost, toString_templ(now.templ), now.rem);
if (mcos[now.node][now.templ][now.rem] < now.cost) continue;
for (const pii &e : G[now.node])
{
val nxt = e.se;
val ncos = e.fi + now.cost;
val nxtRem = getNextRem(now.rem, e.fi, templ[nxt]);
val nxtT = getNextTempl(now.templ, templ[nxt]);
if (!canGoto(now, templ[nxt], e.fi)) { continue; }
if (chmin(mcos[nxt][nxtT][nxtRem], ncos)) {
pq.emp(ncos, nxt, nxtT, nxtRem);
}
}
}
return;
}
void Xx_main_xX()
{
cin >> N >> M >> X;
rep(i, N) {
cin >> templ[i];
}
rep(i, M) {
int s, t, c;
cin >> s >> t >> c;
--s, --t;
G[s].eb(c, t);
G[t].eb(c, s);
}
dijkstra(0);
int ans = INF;
rep(t, 3) {
rep(rem, 201) {
chmin(ans, mcos[N-1][t][rem]);
}
}
outl(ans);
return;
}
} // {{{
signed main(){cout << fixed << setprecision(9); ydk::Xx_main_xX(); return 0;} // }}}

ステータス

項目 データ
問題 0006 - ヘビの JOI 君 (Snake JOI)
ユーザー名 Arumakan_ei1727
投稿日時 2018-11-21 18:18:50
言語 C++14
状態 Accepted
得点 100
ソースコード長 3919 Byte
最大実行時間 99 ms
最大メモリ使用量 26960 KB

セット

セット 得点 Cases
1 set1 20 / 20 *t6*1.txt
2 set2 20 / 20 *t6*2.txt
3 set3 20 / 20 *t6*3.txt
4 set4 20 / 20 *t6*4.txt
5 set5 20 / 20 *t6*5.txt

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
2017-yo-t6-in1.txt AC 71 ms 25820 KB
1
2017-yo-t6-in2.txt AC 99 ms 25948 KB
2
2017-yo-t6-in3.txt AC 75 ms 26284 KB
3
2017-yo-t6-in4.txt AC 63 ms 26724 KB
4
2017-yo-t6-in5.txt AC 65 ms 26960 KB
5