Contest Duration: - (local time) (100 minutes) Back to Home

Submission #7767964

Source Code Expand

Copy
```#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>

using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007
#define P pair<ll, ll>

ll n, m;

ll d[1100][1100]; // 結果
struct edge { ll to, cost; };
vector<edge> g[1100][1100]; //隣接リスト to, cost
void dijkstra(ll k, ll a) {
priority_queue<P, vector<P>, greater<P> > q;
fill(d[k], d[k] + n + 10, INF);
d[k][a] = 0;
q.push(P(0, a));
while (!q.empty()) {
P p = q.top();
q.pop();
ll v = p.second;
if (d[k][v] < p.first) continue;
REP(i, g[k][v].size()) {
edge e = g[k][v][i];
if (d[k][e.to] > d[k][v] + e.cost) {
d[k][e.to] = d[k][v] + e.cost;
q.push(P(d[k][e.to], e.to));
}
}
}
}

vector<P> t;
vector<ll> s[1100], ans2;
ll st;

void dfs(ll a, ll b) {
REP(i, s[a].size()) {
//cout << d[st][s[a][i]] << endl;
if (d[st][s[a][i]] == b - 1) {
//cout << "aaaa" << endl;
ans2.push_back(s[a][i]);
dfs(s[a][i], b - 1);
break;
}
}
}

int main() {
cin >> n >> m;
REP(i, m) {
ll a, b;
cin >> a >> b;
a--;
b--;
t.push_back(P(a, b));
s[b].push_back(a);
}
ll ans = INF;
REP(i, n) {
REP(j, m) {
ll a = t[j].first, b = t[j].second;
if (b == i)g[i][a].push_back({ n, 1 });
else g[i][a].push_back({ b, 1 });
}
dijkstra(i, i);
if (ans > d[i][n]) {
ans = d[i][n];
st = i;
}
}
if (ans == INF){
cout << -1 << endl;
return 0;
}
cout << ans << endl;
dfs(st, ans);
REP(i, ans2.size()) {
cout << ans2[i] + 1 << endl;
}
}```

#### Submission Info

Submission Time 2019-09-28 22:36:19+0900 F - Pure kenken714 C++14 (GCC 5.4.1) 600 2046 Byte AC 215 ms 87424 KB

#### Judge Result

Score / Max Score 0 / 0 600 / 600
Status
 AC × 3
 AC × 33
Set Name Test Cases
Sample Sample_01.txt, Sample_02.txt, Sample_03.txt
Subtask1 Sample_01.txt, Sample_02.txt, Sample_03.txt, case_01.txt, case_02.txt, case_03.txt, case_04.txt, case_05.txt, case_06.txt, case_07.txt, case_08.txt, case_09.txt, case_10.txt, case_11.txt, case_12.txt, case_13.txt, case_14.txt, case_15.txt, case_16.txt, case_17.txt, case_18.txt, case_19.txt, case_20.txt, case_21.txt, case_22.txt, case_23.txt, case_24.txt, case_25.txt, case_26.txt, case_27.txt, case_28.txt, case_29.txt, case_30.txt
Case Name Status Exec Time Memory
Sample_01.txt AC 11 ms 28928 KB
Sample_02.txt AC 10 ms 28928 KB
Sample_03.txt AC 11 ms 28928 KB
case_01.txt AC 206 ms 86784 KB
case_02.txt AC 211 ms 87424 KB
case_03.txt AC 212 ms 87168 KB
case_04.txt AC 214 ms 87168 KB
case_05.txt AC 209 ms 86400 KB
case_06.txt AC 213 ms 87040 KB
case_07.txt AC 210 ms 86912 KB
case_08.txt AC 210 ms 86784 KB
case_09.txt AC 215 ms 87424 KB
case_10.txt AC 212 ms 87296 KB
case_11.txt AC 144 ms 85888 KB
case_12.txt AC 145 ms 86528 KB
case_13.txt AC 145 ms 86144 KB
case_14.txt AC 145 ms 86912 KB
case_15.txt AC 147 ms 86016 KB
case_16.txt AC 10 ms 28928 KB
case_17.txt AC 13 ms 37248 KB
case_18.txt AC 14 ms 32640 KB
case_19.txt AC 113 ms 68864 KB
case_20.txt AC 116 ms 68864 KB
case_21.txt AC 113 ms 68864 KB
case_22.txt AC 108 ms 68864 KB
case_23.txt AC 109 ms 68864 KB
case_24.txt AC 112 ms 68864 KB
case_25.txt AC 96 ms 68480 KB
case_26.txt AC 97 ms 68480 KB
case_27.txt AC 96 ms 68480 KB
case_28.txt AC 96 ms 68352 KB
case_29.txt AC 95 ms 68352 KB
case_30.txt AC 87 ms 66176 KB