bfs两次。第一次处理路径长，第二次选边
#include<iostream> #include<string> #include<cstdio> #include<set> #include<stack> #include<list> #include<vector> #include<queue> #include<algorithm> #include<cstring> #include<cmath> #include<fstream> using namespace std; typedef long long ll; const int maxn = 100010,INF = 0x3f3f3f3f; int n,m; int len[maxn]; vector<pair<int,int>> e[maxn]; void prebfs(){ memset(len,-1,sizeof len); queue<int> Q; Q.push (n); len[n] = 0; while(!Q.empty()){ int x = Q.front();Q.pop(); for(int i = 0;i < e[x].size();++i){ int t = e[x][i].first; if (len[t] == -1){ len[t] = len[x] + 1; Q.push(t); } } } printf("%d\n",len[1]); } void solve(){ queue<int> q; bool vis[maxn] = {0,1}; q.push(1); int le = len[1]; while(le){ int minc = 0x3f3f3f3f; vector<int> next; while(!q.empty()){ int x = q.front();q.pop(); if (x == n) break; for(int i = 0;i < e[x].size();++i){ int p = e[x][i].first,c = e[x][i].second; if (len[p] != len[x] - 1) continue; if (minc < c) continue; if (minc > c){ minc = c; next.clear(); } next.push_back(p); } } if (le != len[1]) printf(" "); printf("%d",minc); for(int i = 0;i < next.size();++i) { if (!vis[next[i]]){ vis[next[i]] = true; q.push(next[i]); } } le--; } puts(""); } void init(){ for(int i = 0;i < maxn;++i) e[i].clear(); int a,b,c; for(int i = 0;i < m;++i){ scanf("%d%d%d",&a,&b,&c); if (a != b){ e[a].push_back({b,c}); e[b].push_back({a,c}); } } prebfs(); solve(); } int main(){ while(cin >> n >> m) init(); }