[SPFA (Bellman Ford)] POJ 1860 Currency Exchange | POJ 3259 Wormholes | LightOJ 1074 Extended

POJ 3259 Wormholes

• 判断是否存在负环（从任源点出发），每个节点作源进行SPFA显然会TLE。
• 只进行一次单源SPFA：
  • 添加辅助顶点C，有向边S->C，有向边C->v (其中v∈V - {S} )。即可只进行一次单源SPFA；
  • 同时防止因添加顶点C引入了负环，因此：
  • 这些有向边的权重ω要足够大，满足2ω>MAX_NW（负权边的绝对值的最大值）。

/* #include 省略 */
typedef pair Pair;
const int MAX_N = 503;
int N;// fields, 1~500
int M;// paths
int W;// wormholes
int G[MAX_N][MAX_N];
int dis[MAX_N];
bool vis[MAX_N];
int cnt[MAX_N];
bool SPFA(int s){
    dis[s]=0;
    priority_queue,greater> Q;// min heap
    Q.push(Pair(dis[s],s));
    vis[s]=true;
    cnt[s]++;
    while(!Q.empty()){
        Pair p = Q.top();
        Q.pop();
        int cur = p.second;
        vis[cur]=false;
        for(int i=1;i<=N+1;i++){
            if(G[cur][i]>10000) continue;
            if(dis[cur]+G[cur][i] < dis[i]){
                // printf("%d %d\n", cur,i);
                dis[i] = dis[cur]+G[cur][i];
                if(!vis[cur]){
                    Q.push(Pair(dis[i],i));
                    vis[i]=true;
                    if(++cnt[i] > N+1-1) return true;
                }
            }
        }
    }
    return false;
}

int main(){
    int F;
    scanf("%d",&F);
    for(int f=0;f10000)? T : min(G[S][E],T);
        }
        for(int w=0;w10000)? (-1)*T : min(G[S][E],(-1)*T);
        }
        // 辅助节点到各节点的边权设置
        G[1][N+1]=10000;
        for(int i=2;i<=N;i++) G[N+1][i]=10000;
        
        fill(dis,dis+MAX_N,999999999);
        fill(vis,vis+MAX_N,false);
        fill(cnt,cnt+MAX_N,0);
        if(SPFA(1)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

LightOJ 1074 Extended Traffic

相较于判断是否存在负环，不同之处在于

typedef pair Pair;
const int INF=0x3fffffff;
const int MAX_N=203;
int N;// n junction
int M;// n roads
int Q;// n queries
int bsns[MAX_N];
int G[MAX_N][MAX_N];
int dis[MAX_N];
int vis[MAX_N];
int cnt[MAX_N];
int cube(int src,int dst){// how to deal with negative val
    int tmp = bsns[dst]-bsns[src];
    return tmp*tmp*tmp;
}
void spfa(){
    dis[1]=0;
    priority_queue,greater > Q;// min heap
    Q.push(Pair(dis[1],1));
    vis[1]=1;
    cnt[1]++;
    while(!Q.empty()){
        Pair p = Q.top();
        Q.pop();
        int cur = p.second;
        vis[cur]=0;
        for(int i=1;i<=N;i++){
            if(G[cur][i]==0) continue;
            if(dis[cur] + cube(cur,i) < dis[i]){
                dis[i] = dis[cur] + cube(cur,i);
                if(!vis[i]) {
                    // 当发现有负环时不应return，而是continue
                    // 应使负环可达的所有点的cnt都 > N-1
                    if(cnt[i]++ > N-1) continue;
                    Q.push(Pair(dis[i],i));
                    vis[i]=1;
                    // 判断是否存在负环的模板做法：
                    // if(cnt[i]++ > N-1) return;
                }
            }
        }
    }
    return;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        fill(G[0],G[0]+MAX_N*MAX_N,0);fill(dis,dis+MAX_N,INF);fill(vis,vis+MAX_N,0);
        fill(cnt,cnt+MAX_N,0);
        scanf("%d",&N);
        for(int n=1;n<=N;n++) scanf("%d",&bsns[n]);
        scanf("%d",&M);
        for(int m=1;m<=M;m++){
            int src,dst; scanf("%d %d",&src,&dst);
            G[src][dst]=1;// uni-directional
        }
        spfa();
        printf("Case %d:\n", t);
        scanf("%d",&Q);
        for(int q=0;qN-1
            if(dis[x]<3 || dis[x]==INF ||cnt[x]>N-1) printf("?\n");
            else printf("%d\n", dis[x]);
        }
    }
    return 0;
}