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
Task F - Pure
User kenken714
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2046 Byte
Status AC
Exec Time 215 ms
Memory 87424 KB

Judge Result

Set Name Sample Subtask1
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