我的思路是bfs/dfs+spfa
第一遍判断每个点能否到达n
第二遍找出:每个点,能到达这个点的所有点中价格最小是多少,在这个点卖掉最多能赚多少钱
上代码:(前面一大坨自定义不要管^_^
1 #include2 namespace ZDY{ 3 #define fre freopen("test.in","r",stdin) 4 #define ll long long 5 #define db double 6 #define Fur(i,x,y) for(int i=x;i<=y;i++) 7 #define fur(i,x,y) for(i=x;i<=y;i++) 8 #define Fdr(i,x,y) for(int i=x;i>=y;i--) 9 #define in2(x,y) in(x),in(y)10 #define in3(x,y,z) in2(x,y),in(z)11 #define in4(a,b,c,d) in2(a,b);in2(c,d)12 #define clr(x,y) memset(x,y,sizeof(x))13 #define cpy(x,y) memcpy(x,y,sizeof(x))14 #define fl(i,x) for(int i=head[x],to;to=e[i].to,i;i=e[i].nxt)15 #define inf 214748364716 }17 namespace FAST{18 #define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0)19 #define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0)20 #define gc ((*fib::f)?(*(fib ::f++)):(fgets(fib::b,sizeof(fib::b),stdin)?(fib::f=fib::b,*(fib::f++)):-1))21 namespace fib{ char b[300000]= {},*f=b;}namespace fob{ char b[300000]= {},*f=b,*g=b+300000-2;}struct foce{~foce(){pob;fflush(stdout);}} _foce;namespace ib{ char b[100];}template inline void in(T &x){x=0;char c;bool f=0;while((c=gc)>'9'||c<'0')if(c=='-')f=!f;x=c-48;while((c=gc)<='9'&&c>='0')x=x*10+c-48;if(f)x=-x;}template inline void out(T x){ if(x==0){pc(48);return;}if(x<0){pc('-');x=-x;}char *s=ib::b;while(x) *(++s)=x%10,x/=10;while(s!=ib::b) pc((*(s--))+48);}template inline void outn(T x){ out(x);pc('\n');}inline char sc(){ char c=gc;while(!(('A'<=c&&c<='Z')||('a'<=c&&c<='z')||('0'<=c&&c<='9')))c=gc;return c;}22 template inline T ABS(T x){ return x>0?x:-x;}23 template inline T MAX(T x,T y){ return x>y?x:y;}24 template inline T MIN(T x,T y){ return x inline T GCD(T x,T y){ return y?GCD(y,x%y):x;}26 template inline void swap(T x,T y){T t=x;y=t;x=y;}27 }using namespace FAST;using namespace ZDY;using namespace std;28 #define N 10000129 int val[N],head[N],Head[N],cnt=0,n,m,ans=0,q[N*3],f[N];30 bool b[N],v[N];31 struct edge{ int nxt,to;}e[1000001],E[1000001];32 inline void add(int x,int y){33 e[++cnt].to=y;E[cnt].to=x;34 e[cnt].nxt=head[x];E[cnt].nxt=Head[y];35 head[x]=Head[y]=cnt;36 }37 inline void bfs(){38 int h=0,t=1,x;39 q[0]=n;b[n]=1;40 while(h