1 条题解

  • 0
    @ 2024-12-24 10:06:04

    C++ :

    //ALGORIHTM::DC
    //AUTHOR::STDAFX
    
    #define MAXE 50000UL
    #define MAXN 2000UL
    #define INF 100000000L
    
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    bool SPFA();
    
    struct Edge{
    	int v,nx,w;
    };
    
    struct stack{
    	int head,data[MAXE];
    	inline int top(){
    		return data[head];
    	}
    	inline bool empty(){
    		return head==0;
    	}
    	inline void pop(){
    		head--;
    		return;
    	}
    	inline void push(int temp){
    		data[++head]=temp;
    		return;
    	}
    };
    
    Edge edge[MAXE];
    
    int n,ml,md,indgr[MAXN],headlist[MAXN],a,b,k,ec,dx[MAXN];
    
    bool ex[MAXN];
    
    stack sta;
    
    int main(){
    	scanf("%d%d%d",&n,&ml,&md);
    	for(int i=1;i<=ml;i++){
    		//a->b w=k;
    		scanf("%d%d%d",&a,&b,&k);
    		edge[++ec].v=b;
    		edge[ec].w=k;
    		edge[ec].nx=headlist[a];
    		headlist[a]=ec;
    	}
    	for(int i=1;i<=md;i++){
    		//b->a w=-k
    		scanf("%d%d%d",&a,&b,&k);
    		edge[++ec].v=a;
    		edge[ec].w=-k;
    		edge[ec].nx=headlist[b];
    		headlist[b]=ec;
    	}
    	for(int i=1;i<n;i++){
    		//i+1->i
    		edge[++ec].v=i;
    		edge[ec].w=0;
    		edge[ec].nx=headlist[i+1];
    		headlist[i+1]=ec;
    	}
    	if(!SPFA()){
    		printf("-1");
    	}
    	else if(dx[n]>INF){
    		printf("-2");
    	}
    	else{
    		printf("%d",dx[n]);
    	}
    	return 0;
    }
    
    bool SPFA(){
    	memset(dx,50,sizeof(dx));dx[1]=0;
    	sta.push(1);
    	while(!sta.empty()){
    		k=sta.top();sta.pop();ex[k]=0;
    		for(int i=headlist[k];i!=0;i=edge[i].nx){
    			if(dx[edge[i].v]>dx[k]+edge[i].w){
    				dx[edge[i].v]=dx[k]+edge[i].w;
    				if(!ex[edge[i].v]){
    					indgr[edge[i].v]++;
    					if(indgr[edge[i].v]>n){
    						return false;
    					}
    					ex[edge[i].v]=1;
    					sta.push(edge[i].v);
    				}
    			}
    		}
    	}
    	return true;
    }
    
    • 1

    信息

    ID
    1856
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者