[graph theory] [shortest path] Island Escape

preface

Konjaku original
U63277 Island Escape

Description

There are \ (n \) islands and \ (m \) paths. For some reason, you are transported to the \ (r \) island. You must escape here. There is a damaged portal (but you can repair it) on the \ (c \) island, so your goal is to reach the \ (c \) island. You have a magic value \ (t \). Due to your limited ability, if you want to repair the portal, your magic value must be positive. There is a path and a value \ (z_i \) from island \ (x_i \) to island \ (y_i \). When you go from island \ (x_i \) to island \ (y_i \) (or from island \ (y_i \) to island \ (x_i \), your magic value \ (t \) needs to be multiplied by \ (z_i \), \ (z_i \) may be a negative number, so your magic value \ (t \) may also be negative. You can repeat a path many times.

Now you have to go from island \ (r \) to island \ (c \), because the portal is damaged, so when you reach island \ (c \), your current magic value \ (t \) is positive, and you can repair the portal.

Now I want you to find out the minimum magic value after escaping from here. If you can't escape, output \ (- 1 \).

Input

Line \ (1), two numbers, \ (n \), \ (m \) (\ (5 < = n < = 3000, n < = m < = 6000 \)), indicating that there are \ (n \) Islands;
Line \ (2\)~\(n+1 \), three numbers in each line, \ (x_i \), \ (y_i \), \ (z_i \) (\ (1 \) < = \ (x_i \), \ (y_i \) < = \ (n \), \ (- 10 \) < = \ (z_i \) < = \ (10 \) and \ (z_i ≠ 0 \), indicating that there is a road from the \ (x_i \) island to the \ (y_i \) island, and the value of this road is \ (zi \);
Line \ (n\)+\(3 \), two numbers, \ (r \), \ (c \), represent the island from \ (r \) to \ (c \).

Output

A minimum positive number \ (t \) or \ (- 1 \).

Sample

Input

Sample Input#1

  3 3
  1 2 -1
  2 3 -2
  1 3 4
  1 3

Sample Input#2

  3 3
  1 2 -2
  2 3 2
  1 3-2
  1 3

Sample Input#3

  5 8
  2 3 4
  1 3 3
  2 4 -2
  1 4 -5
  3 5 -1
  2 5 -2
  1 5 3
  4 5 2
  1 2

Output

Sample Output#1

  4

Sample Output#2

  -1

Sample Output#3

  6

Explanation

Sample explanation#1

\(1-2-3\)

Sample explanation#2

The results of both paths are \ (- 4 \) and \ (- 2 \), which are not positive numbers, so output \ (- 1 \)

Sample explanation#2

\(1-3-5-2\)

Train of Thought

The trouble is Gao Jing
Let's build a graph of \ (2n \), where \ (1 \) to \ (n \) are positive numbers and \ (n+1 \) to \ (2n \) are negative numbers
If a negative number is encountered during SPFA, the region will be skipped
It means to build an edge after reading in
If it is a positive number, the undirected edge between the negative number area and the positive number area is built (because the positive number \ (* \) is positive \ (= \) is positive; Negative number \ (* \) positive number \ (= \) negative number)
If it is a negative number, build the undirected edge of the positive number area leading to the negative number area and the negative number area leading to the positive number area (because the positive number \ (* \) negative number \ (= \) negative number; Negative number \ (* \) negative number \ (= \) positive number)
SPFA or normal SPFA
In particular, high-precision pressurization is required
In addition, when building the undirected edge of negative numbers, we should take the absolute value, because it is divided into positive and negative areas

Konjaku may not speak very clearly. You can ask me in the comments or have a private chat with me (852671959)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const ll N=4010,M=25010,W=300,Y=1e10;
struct BNN{
	ll val[W];
}f[N*2];
BNN operator *(BNN &a,ll &b)//Redefine * as high precision multiplication
{
	BNN ans;ll g=0;
	for(ll i=0;i<W;i++)
	{
		ans.val[i]=a.val[i]*b+g;
		g=ans.val[i]/Y;
		ans.val[i]%=Y;
	}
	return ans;
}
bool operator <(BNN &a,BNN &b)//Redefine<
{
	for(ll i=W-1;i>=0;i--)
	{
		if(a.val[i]>b.val[i]) return false;
		else if(a.val[i]<b.val[i]) return true;
	}
	return false;
}
void dy(BNN &a,BNN b)//Assign array b to array a
{
    for(ll i=0;i<W;i++)
        a.val[i]=b.val[i];
}
struct node//Adjacency table
{
    ll to,next,w;
}a[M*2];
ll ls[2*N],tot,n,m,r,c;
bool v[2*N];
queue<int> q;
void addl(ll x,ll y,ll w)
{
    a[++tot].to=y;
    a[tot].next=ls[x];
    ls[x]=tot;
    a[tot].w=w;
}
void SPFA()//SPFA
{
    for(ll i=1;i<=2*n;i++)
      f[i].val[W-1]=999;
    f[r].val[W-1]=0;
    f[r].val[0]=1;
    q.push(r);
    while(!q.empty())
    {
        ll x=q.front();q.pop();
        for(ll i=ls[x];i;i=a[i].next)
        {
            ll y=a[i].to;BNN z=f[x]*a[i].w;
	            if(z<f[y]){
                dy(f[y],z);
                if(!v[y]){
                    v[y]=true;
                    q.push(y);
                }
            }
        }
        v[x]=false;
    }
}
void write(BNN as)
{
	if(as.val[W-1]==999){printf("-1");return;}//Judge whether it is 0
	ll w=W-1;
    while(!as.val[w]) w--;
	printf("%lld",as.val[w]);
    while(w--)//Pressure position
    {
        if(as.val[w]<1e8) putchar('0');
        if(as.val[w]<1e7) putchar('0');
        if(as.val[w]<1e6) putchar('0');
        if(as.val[w]<1e5) putchar('0');
        if(as.val[w]<1e4) putchar('0');
        if(as.val[w]<1e3) putchar('0');
        if(as.val[w]<1e2) putchar('0');
        printf("%lld",as.val[w]);
    }
}
int main()
{
	freopen("date.in","r",stdin);
	freopen("date.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=m;i++){
        ll x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        if(z>0){
            addl(x,y,z);
            addl(y,x,z);
            addl(x+n,y+n,z);
            addl(y+n,x+n,z);//Edge assignment (positive)
        }
        else{
        	z=abs(z);//See above (Ideas)
            addl(x,y+n,z);
            addl(y,x+n,z);
            addl(x+n,y,z);
            addl(y+n,x,z);//Edge assignment (negative)
        }
    }
    scanf("%lld%lld",&r,&c);
    SPFA();
    write(f[c]);//High precision output
    return 0;
}

Posted by Karamja on Sat, 21 May 2022 05:26:07 +0300