這題開始用沒有優(yōu)化的迪杰斯特拉喜聞樂見的超時了，然后我用bellmanford算法按理說時間復(fù)雜度更大但是書上說往往只要很短的時間就可以求出最短路。

所以我用了這個算法但是我對這個算法還是不熟套了模板。這題數(shù)據(jù)應(yīng)該出水了，不然這個算法時間復(fù)雜度挺高的，應(yīng)該過不了。應(yīng)該是迪杰斯特拉的優(yōu)化，一會寫個迪杰斯特拉的優(yōu)化后的算法看看應(yīng)該可以過。

Dijkstra：適用于權(quán)值為非負(fù)的圖的單源最短路徑，用斐波那契堆的復(fù)雜度O(E+VlgV)

BellmanFord：適用于權(quán)值有負(fù)值的圖的單源最短路徑，并且能夠檢測負(fù)圈，復(fù)雜度O(VE) SPFA：適用于權(quán)值有負(fù)值，且沒有負(fù)圈的圖的單源最短路徑，論文中的復(fù)雜度O(kE)，k為每個節(jié)點(diǎn)進(jìn)入Queue的次數(shù)，且k一般<=2，但此處的復(fù)雜度證明是有問題的，其實(shí)SPFA的最壞情況應(yīng)該是O(VE). Floyd：每對節(jié)點(diǎn)之間的最短路徑。

/*
ID: jinbo wu
TASK:butter
LANG:C++
*/
#include<bits/stdc++.h>
using namespace std;
int n,p,c;
vector<pair<int,int> >g[805];
int a[805];
bool vis[805];
int d[805];
int Bellman_Ford(int m)
{queue<int> q;for(int i=0;i<=p;i++) d[i]=(i==m? 0 : 10000);q.push(m);while(!q.empty()){int x=q.front(); q.pop();vis[x]=0;for(int i=0;i<g[x].size();i++){int v=g[x][i].first;if(d[v]>d[x]+g[x][i].second){d[v]=d[x]+g[x][i].second;if(!vis[v]){vis[v]=1;q.push(v);}}}}int ans=0;for(int i=1;i<=n;i++)ans+=d[a[i]];return ans;
}
int main()
{freopen("butter.in","r",stdin);freopen("butter.out","w",stdout);int u,v,w;cin>>n>>p>>c;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=c;i++){cin>>u>>v>>w;g[u].push_back(make_pair(v,w));g[v].push_back(make_pair(u,w));}int ans=1000000;for(int i=1;i<=p;i++){int temp=Bellman_Ford(i);ans=min(ans,temp);}cout<<ans<<endl;}

這是該程序的運(yùn)行時間

下面是用迪杰斯特拉算法經(jīng)過優(yōu)選隊(duì)列優(yōu)化過后的代碼

/*
ID: jinbo wu
TASK:butter
LANG:C++
*/
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> > g[805];
int n,p,c;
bool done[805];
int d[805];
int a[805];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > q;
int dij(int m)
{memset(done,0,sizeof(done));for(int i=1;i<=p;i++) d[i]=(i==m ? 0 :10000);q.push(make_pair(d[m],m));while(!q.empty()){pair<int,int>  u=q.top();q.pop();int x=u.second;if(done[x]) continue;done[x]=1;for(int i=0;i<g[x].size();i++){int v=g[x][i].first;if(d[v]>d[x]+g[x][i].second){d[v]=d[x]+g[x][i].second;q.push(make_pair(d[v],v));}}}int ans=0;for(int i=1;i<=n;i++)ans+=d[a[i]];return ans;}
int main()
{freopen("butter.in","r",stdin);freopen("butter.out","w",stdout);int u,v,w;cin>>n>>p>>c;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=c;i++){cin>>u>>v>>w;g[u].push_back(make_pair(v,w));g[v].push_back(make_pair(u,w));}int ans=10000000;for(int i=1;i<=p;i++){int temp=dij(i);ans=min(ans,temp);}cout<<ans<<endl;
}

經(jīng)過優(yōu)化過后的迪杰斯特拉為什么沒有bellman_ford快？，普通迪杰斯特拉算法到test7的時候就0.5s多test8就超時了。

總結(jié)

以上是生活随笔為你收集整理的usaco Sweet Butter（迪杰斯特拉（优先队列优化），bellman_ford算法模板）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。