PTA 旅游规划(dijkstra+优先队列)_pta dijk 4 5 1 2 3 1 3 7 1 4 50 2 3 4 3 4 2

PTA旅游规划
题意就是给你一些点和边，告诉你两个点之间的距离和价钱，求从起点到终点最短的路径和对应的价钱，如果有多条相同大小的路径，则求出最小的价钱的路径。

可以用dijkstra+优先队列来求解，在原来的基础上增加价值这个权重就好。

#include<bits/stdc++.h>
using namespace std;
const int maxn=510;
int d[maxn],vis[maxn],c[maxn];
int n,m,st,ed;
struct node{
   int v,w,cost;
   node(int a,int b,int c){
   	v=a;
   	w=b;
   	cost=c;
   }
   bool operator <(const node &n)const{
   	if(w==n.w)return cost>n.cost;//价钱从小到大
   	else return w>n.w;//距离从小到大
   }
};

vector<node>adj[maxn];
priority_queue<node>q;
void dijkstra()
{
  memset(d,0x3f,sizeof(d));
   d[st]=0;
   c[st]=0;
   q.push(node(st,d[st],c[st]));
    while(!q.empty()){

	int u=q.top().v;
	q.pop();
	if(u==ed)return ;
	if(vis[u])continue;
	vis[u]=1;
	for(int i=0;i<adj[u].size();i++){
		int x=adj[u][i].v;
		int y=adj[u][i].w;
		int z=adj[u][i].cost;
		if(d[x]>d[u]+y){
			d[x]=d[u]+y;
			c[x]=c[u]+z;
		 q.push(node(x,d[x],c[x]));
		}
		else if(d[x]==d[u]+y&&c[x]>c[u]+z){
			c[x]=c[u]+z;
			//d[x]=d[u]+y;这句可要可不要。
			q.push(node(x,d[x],c[x]));
		}


	}

   }
}
int main(){
    cin>>n>>m>>st>>ed;
    for(int i=0;i<m;i++)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        adj[a].push_back(node(b,c,d));
        adj[b].push_back(node(a,c,d));
    }
       dijkstra();
        cout<<d[ed]<<" "<< c[ed]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65