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
|