Floyd（這個優(yōu)化很牛逼啊）

#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <iomanip> #include <climits> using namespace std; int map[550][550],n,m,w; int main(int argc, char *argv[]) {int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&w);for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)if(i==j)map[i][j]=0;elsemap[i][j]=1e9;for(int i=0;i<m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);if(map[x][y]>z)map[x][y]=map[y][x]=z;}for(int i=0;i<w;i++){int x,y,t;scanf("%d%d%d",&x,&y,&t);if(map[x][y]>-t)map[x][y]=-t;}int flag=0;for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(map[i][j]>map[i][k]+map[k][j])map[i][j]=map[i][k]+map[k][j];}if(map[i][i]<0){printf("YES\n");flag=1;break;}}if(flag)break;}if(!flag){printf("NO\n"); }}return 0; }

spfa（通過每個點進入隊列最多n-1來判斷）

#include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <iomanip> #include <climits> using namespace std; int n,m,w,d[1000],inq[1000],cnt[1000]; vector<pair<int,int> >e[1000]; int spfa() {queue<int>q;q.push(1);inq[1]=1;cnt[1]++;d[1]=0;while(!q.empty()){int now=q.front();q.pop();inq[now]=0;for(int j=0;j<e[now].size();j++){int v=e[now][j].first;if(d[v]>d[now]+e[now][j].second){d[v]=d[now]+e[now][j].second;if(inq[v]==1)continue;inq[v]=1;q.push(v);cnt[v]++;if(cnt[v]>n)return 1;} }}return 0; } int main(int argc, char *argv[]) {int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&w);for(int i=0;i<=n;i++){e[i].clear();inq[i]=0;d[i]=1e9;cnt[i]=0;}for(int i=0;i<m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);e[x].push_back(make_pair(y,z));e[y].push_back(make_pair(x,z));}for(int i=0;i<w;i++){int x,y,t;scanf("%d%d%d",&x,&y,&t);e[x].push_back(make_pair(y,-t));}int flag=spfa(); if(!flag)printf("NO\n");elseprintf("YES\n");}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/huluxin/p/9783886.html

總結(jié)

以上是生活随笔為你收集整理的POJ 3259的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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