用DijAC这题

bus_station @ 2019-12-06 21:59:49

by Hydrate @ 2019-12-06 22:02:08

是不能跑负环, 不是负边权 ...

by NaCly_Fish @ 2019-12-06 22:04:45

@北辰yama 负权也不行。

by Magallan_forever @ 2019-12-06 22:05:05

@gxjtxdy20081202 因为数据水

by bus_station @ 2019-12-06 22:05:13

神鱼！

by Hydrate @ 2019-12-06 22:08:03

嗯, 好吧, 负权确实不行, 不过本题中只存在一条路径, 所以可以用 Dij

by jijidawang @ 2020-01-17 14:26:47

SPFA

@gxjtxdy20081202

#include<iostream>
#include<cstring>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#define INF 2147483647
using namespace std;
typedef long long ll;
namespace IO
{
    template<typename T>
    inline void read(T &x)
    {
        x=0;
        int f=0;
        char ch=getchar();
        while(!(ch>='0'&&ch<='9')){f|=(ch=='-');ch=getchar();}
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
        x=f?-x:x;
    }
    template<typename T> 
    inline void write(T x)
    {
        if(x<0) {putchar('-');x=-x;}
            if(x>=10) write(x/10);
        putchar(x%10+'0');
    }
}
using namespace std;
struct Edge
{
    int z;
    int val;
    int nexty;
}edge[1000000];
int head[20000];
int cnt=0;
inline void add(int a,int b,int c)
{
    cnt++;
    edge[cnt].z=b;
    edge[cnt].val=c;
    edge[cnt].nexty=head[a];
    head[a]=cnt;
}
int GetAns(int a,int b)
{
    bool visit[20000]={0};
    ll dis[20000];
    int n,m,s;
    n=3,m=2,s=1;
    for(int i=1;i<=n;i++) dis[i]=INF;
    add(1,2,a);add(2,3,b);
    int curr=s;
    dis[s]=0;
    ll minn;
    while (!visit[curr])
    {
        visit[curr]=true;
        for (int i=head[curr];i!=0;i=edge[i].nexty)
        {
            if(!visit[edge[i].z]&&dis[edge[i].z]>dis[curr]+edge[i].val)
            dis[edge[i].z]=dis[curr]+edge[i].val;
        }
        minn=INF;
        for (int i=1;i<=n;i++)
        {
            if (!visit[i]&&minn>dis[i])
            {
                minn=dis[i];
                curr=i;
            }
        }
    }
    return dis[3];
}
int main()
{
    int A,B;
    IO::read(A),IO::read(B);
    IO::write(GetAns(A,B));
    return 0;
}