Записи в блоге

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
8	ecnerwala	3494
9	Um_nik	3396
10	gamegame	3386

№	Пользователь	Вклад
1	Um_nik	163
1	maomao90	163
3	-is-this-fft-	162
4	atcoder_official	158
4	cry	158
6	awoo	157
7	nor	155
7	adamant	155
9	TheScrasse	153
10	maroonrk	152

i was solving problem D-SCORE ATTACK of ABC 061 and i tried implementing classic bellman ford algorithm by changing the weight to -ve weight ,so as if any negative cycle occurs then that means score will be continuously increasing but i am getting WA ,i don't know where i am making mistake and i have assumed that graph is connected so either my assumption is wrong or i am implementing wrong algorithm .please can you guys help ? sorry if my english is bad.

here is my code

#include "bits/stdc++.h"
using namespace std;
typedef long long int ll;
const ll maxn=1e12;
int main()
{

    ll n,m;cin>>n>>m;
    vector<tuple<ll,ll,ll>>v(m);
    for(ll i=0,x,y,z;i<m;++i)
    {
        cin>>x>>y>>z;
        v[i]=make_tuple(x,y,-z);
    }
    vector<ll>dis(n+1,maxn);
    dis[1]=0;
    for(ll i=1;i<=n;++i)
    {
        int flag=0;
        for(auto x:v)
        {
            ll a,b,c;
            tie(a,b,c)=x;
            if(dis[a]==maxn)continue;
            if(dis[a]+c<dis[b])
            {
                flag=1;
                dis[b]=dis[a]+c;
            }
        }
        if(i==n&&flag==1)
        {
            cout<<"inf"<<endl;return 0;
        }
    }
    cout<<-dis[n]<<endl;
}

Полный текст и комментарии »

Блог пользователя i_love_sharapova