為什么SPFA廢了呢，因為它的時間復雜度不穩定，就是說別人可以完全出一個圖來卡死你，其實SPFA就是Bellman-Ford演算法的佇列優化，在某些情況下跑的比它快，
#include<bits/stdc++.h> using namespace std; int n,m,p,f[1000][1000],dis[1000],amount[1000],visit[1000],path[1000]; queue<int> que; void input() { memset(dis,0x7f,sizeof(dis)); memset(f,0x7f,sizeof(f)); int aa,ss,weight; cin>>n>>m>>p; dis[p]=0; for(int i=1;i<=m;i++) { f[i][i]=0; cin>>aa>>ss>>weight; f[aa][ss]=f[ss][aa]=weight; } for(int i=1;i<=n;i++) path[i]=p; path[p]=0; } bool SPFA(int source) { que.push(source); visit[source]=1; amount[source]++; while(!que.empty()) { int b=que.front(); visit[b]=0; que.pop(); for(int i=1;i<=n;i++) { if(f[b][i]!=0x7f7f) { if(dis[i]>dis[b]+f[b][i]) { dis[i]=dis[b]+f[b][i]; path[i]=b; if(!visit[i]) { que.push(i); amount[i]++; if(amount[i]>=n) return false; visit[i]=1; } } } } } return true; } void dnn(int i) { stack<int> s; cout<<p; while(path[i]!=0) { s.push(i); i=path[i]; } while(!s.empty()) { cout<<"->"<<s.top(); s.pop(); } } void print() { for(int i=1;i<=n;i++) if(i!=p) { cout<<i<<' '<<':'<<' '<<dis[i]<<' '<<"路徑"<<":"<<' '; dnn(i); cout<<endl; } } int main() { input(); if(SPFA(p)) print(); else cout<<"有負權回路！"; return 0; }
很久前學的演算法真是有滿滿的回憶呢！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/69634.html
標籤：其他