hdu 3790 ——最短路径问题（spfa）

淡淡的烟草味﹌ 2024-04-17 22:10 2阅读 0赞

Problem Description

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

Input

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。  
(1<n<=1000, 0<m<100000, s != t)

Output

输出 一行有两个数， 最短距离及其花费。

Sample Input

3 2  
1 2 5 6  
2 3 4 5  
1 3  
0 0

Sample Output

9 11

题解：spfa板子题 ，跑两遍spfa，第一遍spfa更新最短路径 ，第二遍 spfa根据路径相同更新最小花费。

#include<iostream>
    #include<cstring>
    #include<vector>
    #include<queue> 
    using namespace std;
    typedef long long ll;
    const int mmax=1e4+10;
    vector<ll> v1[mmax];
    vector<ll> v2[mmax];
    vector<ll> v3[mmax];
    ll dis[mmax];//距离
    ll cost[mmax]; //花费 
    ll is_vis[mmax];
    ll is_vis1[mmax];
    queue<ll> q,p;
    void init()
    {
    	for(int i=0;i<mmax;i++)
    	{
    		v1[i].clear();
    		v2[i].clear();
    		v3[i].clear();
    	}
    	memset(is_vis,0,sizeof(is_vis));
    	memset(is_vis1,0,sizeof(is_vis1));
    	memset(dis,0x3f,sizeof(dis));
    	memset(cost,0x3f,sizeof(cost));
    	while(!q.empty())
    		q.pop();
    	while(!p.empty())
    		p.pop();	
    }
    void spfa(ll start)
    {
    	q.push(start);
    	is_vis[start]=1;
    	dis[start]=0;
    	while(!q.empty())
    	{
    		ll u=q.front();
    		q.pop();
    		is_vis[u]=0;
    		for(int i=0;i<v1[u].size();i++)
    		{
    			if(dis[v1[u][i]]>dis[u]+v2[u][i])
    			{
    				dis[v1[u][i]]=dis[u]+v2[u][i];
    				if(is_vis[v1[u][i]]==0)
    				{
    					q.push(v1[u][i]);
    					is_vis[v1[u][i]]=1;
    				}
    			} 
    		}
    	}
    	
    	p.push(start);
    	is_vis1[start]=1;
    	cost[start]=0;
    	while(!p.empty())
    	{
    		ll u=p.front();
    		p.pop();
    		is_vis1[u]=0;
    		for(int i=0;i<v1[u].size();i++)
    		{
    			if(dis[v1[u][i]]==dis[u]+v2[u][i]&&cost[v1[u][i]]>cost[u]+v3[u][i])
    			{
    				cost[v1[u][i]]=cost[u]+v3[u][i];
    				if(is_vis1[v1[u][i]]==0)
    				{
    					p.push(v1[u][i]);
    					is_vis1[v1[u][i]]=1;
    				}
    			} 
    		}
    	}
    	
    }
    int main()
    {
    	ios::sync_with_stdio(false);
    	ll n,m;
    	while(cin>>n>>m,n,m)
    	{
    		init();
    		for(int i=1;i<=m;i++)
    		{
    			ll s,e,w,mon;
    			cin>>s>>e>>w>>mon;
    			v1[s].push_back(e);
    			v1[e].push_back(s);
    			v2[s].push_back(w);
    			v2[e].push_back(w);
    			v3[s].push_back(mon);
    			v3[e].push_back(mon);
    		}
    		ll s,t;
    		cin>>s>>t;
    		spfa(t);
    		cout<<dis[s]<<" "<<cost[s]<<endl;
    	}
    	return 0;
    }