L3-040 人生就像一场旅行（Floyd）

张开发
• 2026/4/14 7:42:36 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

L3-040 人生就像一场旅行（Floyd）
刚开始用的朴素版dijkstra 最后一个没过 接着换成了 堆优化版的dijkstra 最后一个也没过然后用Floyd 才过了 思路利用Floyd 确定任意两座城市之间的最少费用和最大心情值.#includebits/stdc.h using namespace std; const int N 510; int d[N][N]; int xin[N][N]; int b,n,m,k; void Floyd() { for(int k 1; k n; k ) for(int i 1; i n; i ) for(int j 1; j n; j ) { if(d[i][j] d[i][k] d[k][j]) { d[i][j] d[i][k] d[k][j]; xin[i][j] xin[i][k] xin[k][j]; } else if(d[i][j] d[i][k] d[k][j]) { if(xin[i][j] xin[i][k] xin[k][j]) { xin[i][j] xin[i][k] xin[k][j]; } } } } int main() { cin b n m k; memset(d,0x3f,sizeof d); for(int i 1; i n; i ) d[i][i] 0; for(int i 1; i m; i ) { int c1,c2,f,x; cin c1 c2 f x; d[c1][c2] d[c2][c1] f; xin[c1][c2] xin[c2][c1] x; } Floyd(); while(k --) { int x; cin x; setintst; int maxn 0; for(int i 1; i n; i ) { if(d[x][i] b i ! x) { st.insert(i); maxn max(xin[x][i],maxn); } } if(st.size()) { vectorintve; int flag 1; for(auto it : st) { if(flag) { cout it; flag 0; } else { cout it; } if(xin[x][it] maxn) ve.push_back(it); } cout \n; for(int i 0; i ve.size(); i ) if(i 0) cout ve[i]; else cout ve[i]; cout \n; } else puts(T_T); } }

更多文章