Extended Traffic

LightOJ-1074

这题因为涉及到减法和三次方，所以可能会出现负圈。
这里使用的算法叫做SPFA算法，这个可以用来判负圈和求解最短路。Bellman-Ford算法和SPFA算法很相似。
这里要注意的是cnt出现次数应该要在哪里加。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<string>

#include<vector>

#include<queue>

using namespace std;

const int INF=0x3f3f3f3f;

const int maxn=202;

int d[maxn];

int n,m;

int a[maxn];

int cnt[maxn];

bool vis[maxn];

bool circle[maxn];

struct edge{

    int to;

    int cost;

};

vector<edge>edges[maxn];

void SPFA(int s){

    memset(d,INF,sizeof(d));

    memset(vis,0,sizeof(vis));

    memset(cnt,0,sizeof(cnt));

    memset(circle,0,sizeof(circle));

    d[s]=0;

    queue<int> q;

    q.push(s);

    vis[s]=1;

    while(!q.empty()){

        int v=q.front();

        q.pop();

        vis[v]=0;

        for(int i=0;i<edges[v].size();i++){

            int u=edges[v][i].to;

            int cost=edges[v][i].cost;

            if(circle[u])

                continue;

            if(d[u]>d[v]+cost){

                d[u]=d[v]+cost;

                if(!vis[u]){

                    q.push(u);

                    vis[u]=1;

                    cnt[u]++;

                }

                if(cnt[u]>n)

                    circle[u]=1;

            }

        }

    }

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    int t;

    cin>>t;

    int k=0;

    while(t--){

        cin>>n;

        for(int i=1;i<=n;i++){

            cin>>a[i];

            edges[i].clear();

        }

        cin>>m;

        for(int i=0;i<m;i++){

            int from,to;

            cin>>from>>to;

            int diff=(a[to]-a[from])*(a[to]-a[from])*(a[to]-a[from]);

            edges[from].push_back({to,diff});

        }

        SPFA(1);

        int q;

        cin>>q;

        cout<<"Case "<<++k<<":"<<endl;

        for(int i=0;i<q;i++){

            int ter;

            cin>>ter;

            if(d[ter]<3||d[ter]==INF||circle[ter]){

                cout<<"?"<<endl;

            }else cout<<d[ter]<<endl;

        }

    }

    return 0;

}

巴特西

LightOJ-1074(SPFA判负圈+Bellman-Ford算法)

Extended Traffic

LightOJ-1074

最新文章

热门文章