PTA 7-9 旅游规划(SPFA)

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入格式:

输入说明：输入数据的第1行给出4个正整数

输出格式:

在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

输出样例:

3 40

题意

求从s点出发到d点的最短路并且最小花费

题解

单源最短路，考虑Dijstra（优化）和SPFA，这里选用SPFA

求最短路不用说

求最小花费，如果到某点的长度相等，更新花费就行了

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N=505,M=N*N,INF=0x3f3f3f3f;
 5 int Vis[N],Dist[N],C[N];
 6 int Cost[N][N],G[N][N];
 7 int n,m,s,d;
 8 void spfa()
 9 {
10     memset(Dist,INF,sizeof(Dist));
11     queue<int> Q;
12     Q.push(s);
13     Dist[s]=0;
14     while(!Q.empty())
15     {
16         int u=Q.front();Q.pop();
17         Vis[u]=0;
18         for(int v=0;v<=n;v++)
19         {
20             if(u!=v&&G[u][v]!=1e9)
21             {
22                 if(Dist[v]>Dist[u]+G[u][v])//最短路
23                 {
24                     Dist[v]=Dist[u]+G[u][v];
25                     C[v]=C[u]+Cost[u][v];//如果更新了最短路，花费直接更新
26                     if(!Vis[v])
27                     {
28                         Q.push(v);
29                         Vis[v]=1;
30                     }
31                 }
32                 else if(Dist[v]==Dist[u]+G[u][v])//最短路相同
33                 {
34                     if(C[v]>C[u]+Cost[u][v])//最小花费
35                     {
36                         C[v]=C[u]+Cost[u][v];
37                         if(!Vis[v])
38                         {
39                             Q.push(v);
40                             Vis[v]=1;
41                         }
42                     }
43                 }
44             }
45         }
46     }
47     printf("%d %d
",Dist[d],C[d]);
48 }
49 int main()
50 {
51     int u,v,w,t;
52     scanf("%d%d%d%d",&n,&m,&s,&d);
53     for(int i=0;i<=n;i++)
54         for(int j=0;j<=n;j++)
55             if(i==j)G[i][j]=Cost[i][j]=0;
56             else G[i][j]=Cost[i][j]=1e9;
57     for(int i=0;i<m;i++)
58     {
59         scanf("%d%d%d%d",&u,&v,&w,&t);
60         Cost[v][u]=Cost[u][v]=t;
61         G[v][u]=G[u][v]=w;
62     }
63     spfa();
64     return 0;
65 }