1 solutions

  • 0
    @ 2025-11-5 16:07:50

    C++ :

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <climits>
    
    using namespace std;
    
    struct bian{
    	int y,next,len;
    }e[45001]={0};
    
    int n,i,j,k,m,tot,x,y,z,st,en,o,tp,p,max,sum;
    int f[1001]={0},g[1001]={0},ng[1001]={0},d[1001]={0},dist[1001]={0};
    bool v[1001]={0};
    int q[100001]={0};
    
    void swap(int &x,int &y)
    {
    	int tp;
    	tp=x;
    	x=y;
    	y=tp;
    }
    
    bool spfa(int x)
    {
    	bool res=false;
    	int i,j,k,st,en,o,p;
    	for(int i=1;i<=n;i++)
    	{
    		dist[i]=INT_MAX;
    	}
    	st=0, en=1, q[en]=x, v[x]=true;
    	d[x]=1, dist[x]=0;
    	while(st!=en)
    	{
    		if(st==100000) st=0;
    		st++;
    		o=g[q[st]];
    		v[q[st]]=false;
    		while(o!=0)
    		{
    			p=e[o].y;
    			if(dist[p]>dist[q[st]]+e[o].len)
    			{
    				dist[p]=dist[q[st]]+e[o].len;
    				if(!v[p])
    				{
    					q[++en]=p;
    					v[p]=true;
    					d[p]++;
    					if(d[p]>n) return true;
    				}
    			}
    			o=e[o].next;
    		}
    	}
    }
    
    void init()
    {
    	cin>>n>>m>>k;
    	for(int i=1;i<=m;i++)
    	{
    		cin>>x>>y>>z;
    		if(y<x) swap(x,y);
    		tot++;
    		e[tot].y=y;
    		e[tot].len=z;
    		e[tot].next=g[x];
    		g[x]=tot;
    	}
    	for(int i=1;i<=k;i++)
    	{
    		cin>>x>>y>>z;
    		tot++;
    		e[tot].y=x;
    		e[tot].len=-z;
    		e[tot].next=g[y];
    		g[y]=tot;
    	}
    	for(int i=2;i<=n;i++)
    	{
    		tot++;
    		e[tot].y=i-1;
    		e[tot].next=g[i];
    		e[tot].len=0;
    		g[i]=tot;
    	}
    	if(spfa(1))
    	{
    		cout<<-1<<endl;
    		return;
    	}
    	if(dist[n]==INT_MAX)
    	{
    		cout<<-2<<endl;
    		return;
    	}
    	cout<<dist[n]<<endl;
    	return;
    }
    
    int main()
    {
    	//freopen("in.txt","r",stdin);
    	//freopen("out.txt","w",stdout);
    	
    	init();
    	
    	return 0;
    }
    
    • 1

    Information

    ID
    17502
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By