源码

#include<bits/stdc++.h>
#define PII pair<int,int>
#define x first
#define y second
using namespace std;

const int N = 110;
struct Node{
    int b , c;
};
vector<Node> e[N];
int n , m , s , ed;
int d[N];
vector<int> pre[N];
vector<vector<int>> paths;
vector<int> temppath;

bool st[N];

void DFS(int v, int s) {
    if(v == s) {

        temppath.push_back(v);
        paths.push_back(temppath);
        temppath.pop_back();
        return;
    }
    temppath.push_back(v);
    for(int i = 0; i < pre[v].size(); i ++) {
        DFS(pre[v][i] , s);
    }
    temppath.pop_back();
}

signed main() {
    cin >> n >> m >> s >> ed;
    for(int i = 1; i <= m; i ++) {
        int a , b , c;
        cin >> a >> b >> c;
        e[a].push_back({b , c});
        e[b].push_back({a , c});
    }

    priority_queue<PII , vector<PII> , greater<PII>> q;
    q.push({0 , s});
    memset(d , 0x3f , sizeof d);
    d[s] = 0;

    while(q.size()) {
        auto t = q.top();
        q.pop();

        if(st[t.y]) continue;
        st[t.y] = 1;

        for(auto tt : e[t.y]) {
            if(d[tt.b] > t.x + tt.c) {
                d[tt.b] = t.x + tt.c;
                q.push({d[tt.b] , tt.b});
                pre[tt.b].clear();
                pre[tt.b].push_back(t.y);
            }
            else if(d[tt.b] == t.x + tt.c) {
                pre[tt.b].push_back(t.y);
            }
        }
    }


    DFS(ed , s);

    for(int i = 0; i < paths.size(); i ++) {
        reverse(paths[i].begin() , paths[i].end());
    }

    sort(paths.begin() , paths.end());

    cout << paths.size() << endl;

    for(int i = 0; i < paths.size(); i ++) {
        cout << s;
        for(int j = 1; j < paths[i].size(); j ++) {
            cout << "->" << paths[i][j];
        }
        if(i < paths.size() - 1) cout << endl;
    }

}

样例输入

4 5 0 2
0 1 2
0 2 5
0 3 1
1 2 1
3 2 2

样例图

样例输出

2
0->1->2 
0->3->2