我的做法：
vector模擬的圖的鏈表結構+SPFA演算法，樣例測驗正確，但測驗是出現Wrong Answer，為什么？
初步思考：是邊界資料的問題？但是如何找出邊界資料？或者是我的SPFA演算法有誤？
求哪位大神幫忙指教？
本人代碼：
#include<iostream>
#include<iomanip>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>//無窮大，無窮小 INT_MAX,INT_MIN
#include<cfloat>//DBL_MAX,-DBL_MAX
using namespace std;
const int N=50020;
struct E {
int next;
int cost;
};
vector<E> edge[N];//圖的鄰接鏈表
int dis[N];//dis[i] 0到i的最短距離
bool vis[N];//訪問標志
bool spfa(int numnode);//numnode 結點總個數
void addEdge(int a,int b,int c) {//添加邊
E e;
e.cost=c;
e.next=b;
edge[a].push_back(e);
}
int main(int argc, char** argv) {
int n;
cin>>n;
int a,b,c;
E e;
int max_v=-1;
for(int i=0; i<N; i++) {
edge[i].clear();
}
while(n--) {
cin>>a>>b>>c;
a+=10;//在原圖處理時,為了避免ai-1==-1,我們令所有ai與bi都自增了10.
b+=10;//所以我們形成了一個具有點[9,max_v]的有向圖(其實就是差分約束系統)
max_v=max(max_v,b);//找出最大值
addEdge(b,a-1,-c);//邊(b,a-1)
}
for(int i=10; i<=max_v; i++) {
addEdge(i,i-1,0);
addEdge(i-1,i,1);
addEdge(0,i,0);
}
addEdge(0,9,0);
//圖的結點總個數0~max_v，是否包含超級源點?
int numnode=max_v+1;
spfa(numnode);
int ret=dis[numnode-1]-dis[9];
cout<<ret<<endl;
return 0;
}
bool spfa(int numnode) {
queue<int> q;
for(int i=0; i<N; i++) {
dis[i]=INT_MAX;
vis[i]=false;
}
dis[0]=0;
vis[0]=true;
q.push(0);
while(!q.empty()) {
int u=q.front();
q.pop();
vis[u]=false;
for(int i=0; i<edge[u].size(); i++) {
bool update=false;
int v=edge[u][i].next;
int c=edge[u][i].cost;
if(dis[u]!=INT_MAX&&dis[v]>dis[u]+c) {//
dis[v]=dis[u]+c;
if(!vis[v]) {
q.push(v);
vis[v]=true;
update=true;
/* if(++cnt[v]>numnode) {
return false;
}*/
}
}
if(!update) {
break;
}
}
}
return true;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/120401.html
標籤：數據結構與算法
上一篇：如何減小Qt生成的exe檔案大小