最短路三巨头

本是古典何须时尚 2022-09-30 13:46 132阅读 0赞

题目链接：[点击打开链接][Link 1]

解题思路：此为最短路径问题

最短时间受人数和路程两个因素影响，因此循环求最短路径时要更新边集。

#include<cstdio>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct aa
    {
    	int u,v,ub,ug,si1,si2,si3;
    };
    
    void bellman_ford(int n,int k,int D[][31],int i,aa a[],int W[])//知道W【】
    {
    	/*int D[31],Father[31];
    	for(int i=1;i<=n;i++)
    		D[i]=99999999;
    	D[s]=0;*/
    
    	for(int node=1;node<=n-1;node++)
    	{
    		for(int j=1;j<=2*k;j++)
    		{
    			if(D[i][a[j].v]>D[i][a[j].u]+W[j])
    			{
    				D[i][a[j].v]=D[i][a[j].u]+W[j];
    				/*cout<<W[j]<<":"<<j<<endl;
    				cout<<a[j].v<<":"<<a[j].u<<endl;
    				cout<<D[i][a[j].v]<<endl;*/
    			}
    		}
    	}                                            
    
    }
    int main()
    {
    	int n,b1,b2,b3,g1,g2,g3;
    	cin>>n>>b1>>b2>>b3>>g1>>g2>>g3;
    	int B[31];
    	for(int i=1;i<=n;i++)
    	cin>>B[i];
        int G[31];
    	for(int i=1;i<=n;i++)
    	cin>>G[i];
    	int k;
    	cin>>k;
    	aa a[110];
    	for(int i=1;i<=k;i++)
    	{
    		cin>>a[i].u>>a[i].v>>a[i].si1>>a[i].si2>>a[i].si3;
    		//a[i].ub=B[a[i].u];
    		//a[i].ug=G[a[i].u];
    
    		a[i+k].v=a[i].u;
    		a[i+k].u=a[i].v;
    		a[i+k].si1=a[i].si1;    
    		a[i+k].si2=a[i].si3;
    		a[i+k].si3=a[i].si2;
    		//a[i+k].ub=B[a[i].v];
    		//a[i+k].ug=G[a[i].v];
    	}
    	
    	/*int G[31][31];
    	for(int i=1;i<=k;i++)                                        
    		for(int j=1;j<=k;j++)
    			G[i][j]=-1;
    	for(int i=1;i<=k;i++)
    		G[a[i].u][a[i].v]=a[i].si1/b1*a[i].ub+a[i].si1/g1*a[i].ug
    		                  +a[i].si2/b1*a[i].ub+a[i].si2/g1*a[i].ug 
    			+a[i].si3/b1*a[i].ub+a[i].si3/g1*a[i].ug;
    			*/
    	
    	/*int W[100];//边的权值
    	for(int i=1;i<=2*k;i++)
    	{
    		W[i]=a[i].si1*b1*a[i].ub+a[i].si1*g1*a[i].ug
    		    +a[i].si2*b2*a[i].ub+a[i].si2*g2*a[i].ug
    			+a[i].si3*b3*a[i].ub+a[i].si3*g3*a[i].ug;
    		cout<<W[i]<<endl;
    	}
    	*/
    	int D[31][31];
    	for(int i=1;i<=n;i++)
    	{
    
    
    		int W[110];
    		for(int e=1;e<=2*k;e++)
    		{
    
    		    W[e]=a[e].si1*b1*B[i]+a[e].si1*g1*G[i]
    				+a[e].si2*b2*B[i]+a[e].si2*g2*G[i]
    				+a[e].si3*b3*B[i]+a[e].si3*g3*G[i];
    			//cout<<W[e]<<' ';
    		}
    		//cout<<endl;
    
    		for(int j=1;j<=n;j++)
    			D[i][j]=99999999;
    		D[i][i]=0;
    		bellman_ford(n,k,D,i,a,W);
    
    		/*for(int j=1;j<=n;j++)
    		cout<<D[i][j]<<' ';
    		cout<<endl;*/
    	}
    	int min=99999999,ans;
    	for(int i=1;i<=n;i++)
    	{
    		int sum=0;
    		for(int j=1;j<=n;j++)
    		{
    			sum+=D[j][i];
    			//cout<<sum<<' ';
    		}
    		//cout<<sum<<' ';
    		//cout<<endl;
    
    		if(sum<min)
    		{
    			min=sum;
    			ans=i;
    		}
    	}
    	/*int min=99999999,ans;
    	for(int i=1;i<=n;i++)
    	{
    		int D[31];
    	    for(int i2=1;i2<=n;i2++)
    		D[i2]=99999999;
    		D[i]=0;
    
    		bellman_ford(n,k,D,a,W);
    
    		int sum=0;
    		for(int j=1;j<=n;j++)
    			sum+=D[j];
    		cout<<sum;
    
    		if(sum<min)
    		{
    			min=sum;
    			ans=a[i].v;
    		}
    	}*/
    	
    	cout<<ans;
    	//system("pause");
    	return 0;
    }

#include <iostream>
    using namespace std;
    struct aa{
        int u,v,flowd,up,down,w;
    };
    void dijkstra(int s,int k,int n,int D[][31],aa a[]){
        for(int i=1;i<=n;i++){
                int min=0x7FFFFFFF,u;
            for(int i1=1;i1<=n;i1++){
                if(D[s][i1]<min){
                    min=D[s][i1];
                    u=i1;
                }
            }
    
            /*从点出发，G[][]式存储
            for(int i2=1;i2<=n;i2++){
                if
            }*/
    
            for(int j=1;j<=2*k;j++){
                if(a[j].u==u&&D[s][a[j].v]>D[s][a[j].u]+a[j].w)
                D[s][a[j].v]=D[s][a[j].u]+a[j].w;
            }
        }
    }
    int main()
    {
        int n,B1,B2,B3,G1,G2,G3;
        cin>>n>>B1>>B2>>B3>>G1>>G2>>G3;
        int X[31];
        int i;
        for(i=1;i<=n;i++)
            cin>>X[i];
        int Y[31];
        for(i=1;i<=n;i++)
            cin>>Y[i];
        int k;
        cin>>k;
        aa a[31];
        for(i=1;i<=k;i++){
            cin>>a[i].u>>a[i].v>>a[i].flowd>>a[i].up>>a[i].down;
            a[i+k].u=a[i].v;
            a[i+k].v=a[i].u;
            a[i+k].flowd=a[i].flowd;
            a[i+k].up=a[i].down;
            a[i+k].down=a[i].up;
        }
    
        int D[31][31];
        for(i=1;i<=n;i++){
    
            for(int j=1;j<=2*k;j++){
                a[j].w=X[i]*(a[j].flowd*B1+a[j].up*B2+a[j].down*B3)
                      +Y[i]*(a[j].flowd*G1+a[j].up*G2+a[j].down*G3);
            }
    
            for(int node=1;node<=n;node++)
            D[i][node]=0x7FFFFFFF;
            D[i][i]=0;
    
            dijkstra(i,k,n,D,a);
    
        }
        int min1=0x7FFFFFFF,ans;
        for(i=1;i<=n;i++){
                int sum=0;
            for(int j=1;j<=n;j++){
                sum+=D[j][i];
            }
            if(sum<min1){
            min1=sum;
            ans=i;
            }
        }
        cout<<ans;
        //system("pause");
        //getchar();
        return 0;
    
    }

**Floyd要用邻接矩阵存储，不适合此题的数据存储。**

[Link 1]: http://www.cogs.pro/cogs/problem/problem.php?pid=21