Submission #79961

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
int s, g;
vector<vector<pair<int, long long>>> G;
vector<long long> dist;
stack<int> st;
stack<int> st2;
 
void dfs(int pos) {
    st.push(pos);
    if (pos == g) {
        while (!st.empty()) {
            st2.push(st.top());
            st.pop();
        }
        return;
    }
    for (int i = 0; i < G[pos].size(); i++) {
        if (dist[G[pos][i].first] == -1) {
            dist[G[pos][i].first] = dist[pos] + G[pos][i].second;
            dfs(G[pos][i].first);
        }
    }
    if (!st.empty()) {
        st.pop();
    }
    return;
}
 
int main() {
    int n, m;
    cin >> n >> m >> s >> g;
    s--, g--;
    G.resize(n);
    dist.assign(n, -1);
    int a, b, c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        a--, b--;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    dist[s] = 0;
    dfs(s);
    cout << dist[g] << "\n";
    while (!st2.empty()) {
        if (st2.size () > 1) {
            cout << st2.top() + 1 << " ";
        } else {
            cout << st2.top() + 1 << "\n";
        }
        st2.pop();
    }
    return(0);
}

ステータス

項目	データ
問題	1814 - 最長経路問題
ユーザー名	woody_1227
投稿日時	2024-07-17 18:12:25
言語	C++17
状態	Accepted
得点	100
ソースコード長	1196 Byte
最大実行時間	156 ms
最大メモリ使用量	13100 KB

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
01.in	AC	24 ms	604 KB	1
02.in	AC	16 ms	700 KB	1
03.in	AC	22 ms	536 KB	1
04.in	AC	20 ms	508 KB	1
05.in	AC	17 ms	608 KB	1
06.in	AC	97 ms	12480 KB	1
07.in	AC	62 ms	7736 KB	1
08.in	AC	68 ms	7364 KB	1
09.in	AC	32 ms	5168 KB	1
10.in	AC	54 ms	5924 KB	1
11.in	AC	43 ms	5716 KB	1
12.in	AC	28 ms	5144 KB	1
13.in	AC	22 ms	4316 KB	1
14.in	AC	40 ms	5520 KB	1
15.in	AC	56 ms	7000 KB	1
16.in	AC	100 ms	13100 KB	1
17.in	AC	81 ms	9256 KB	1
18.in	AC	36 ms	5896 KB	1
19.in	AC	71 ms	8920 KB	1
20.in	AC	45 ms	6720 KB	1
21.in	AC	156 ms	9952 KB	1
22.in	AC	105 ms	9984 KB	1
23.in	AC	107 ms	9892 KB	1
24.in	AC	94 ms	9928 KB	1
25.in	AC	96 ms	9968 KB	1