CCF认证 行车路线

时间：2023-02-02 21:35:17

CCF认证行车路线

行车路线原题连接

描述：

小明和小芳出去乡村玩，小明负责开车，小芳来导航。小芳将可能的道路分为大道和小道。大道比较好走，每走1公里小明会增加1的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走s公里小明会增加s2的疲劳度。例如：有5个路口，1号路口到2号路口为小道，2号路口到3号路口为小道，3号路口到4号路口为大道，4号路口到5号路口为小道，相邻路口之间的距离都是2公里。如果小明从1号路口到5号路口，则总疲劳值为(2+2)^2+2+2^2=16+2+4=22。现在小芳拿到了地图，请帮助她规划一个开车的路线，使得按这个路线开车小明的疲劳度最小。

输入：

输入的第一行包含两个整数n, m，分别表示路口的数量和道路的数量。路口由1至n编号，小明需要开车从1号路口到n号路口。接下来m行描述道路，每行包含四个整数t, a, b, c，表示一条类型为t，连接a与b两个路口，长度为c公里的双向道路。其中t为0表示大道，t为1表示小道。保证1号路口和n号路口是连通的。

输出：

输出一个整数，表示最优路线下小明的疲劳度。

输入样例：

6 7
1 1 2 3
1 2 3 2
0 1 3 30
0 3 4 20
0 4 5 30
1 3 5 6
1 5 6 1

样例输出：

76

思路：

  • 题目中的疲劳度，可以当做距离。大路的长度是固定的，小路的长度与连续行驶的小路距离有关。
  • 数据规模，共有最多500个点，那么可以用dijkstra求最短路的思路来求解。
  • 最原始的dijkstra是点与点之间的长度不变，这里我们就需要考虑长度的变化。可以设一个数组xiaolu[i]，表示到第i个点时已经连续行驶了多长的小路。分类讨论，如果此条路是大路，那么与原始dijkstra一样。如果此条路是小路，那么就要看来的那个点是否从也是从小路过来的，然后才更新最短距离。同时也要更新xiaolu[i]。

源代码：

    #include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;

const long long INF = 1 << 30;
const long long maxn = 505;
struct Edge{
long long type;     //类型
long long len;      //长度
long long to;       //终点
    };
long long n, m;
long long visit[maxn];  //使用的点
long long d[maxn];      //最短距离
long long xiaolen[maxn];//记录连续行驶的小路距离
vector< vector<Edge> > G(maxn);

void dj()
    {
for(long long i = 0; i <= n ;i ++){
            d[i] = INF;
            visit[i] = 0;
            xiaolen[i] = 0;
        }
        d[1] = 0;

while(true){
long long v = -1;

//选未确定的中最近的
for(long long u = 1; u <= n ;u ++){
if(visit[u] == 0){
if(v == -1 || (d[u] < d[v])){
                        v = u;
                    }
                }
            }

if(v == -1){
break;
            }

            visit[v] = 1;
//cout<<"确定的点"<<v<<":距离是"<<d[v]<<endl;
for(long long u = 0; u < G[v].size() ;u ++){
if(G[v][u].type == 0){
//cout<<"到"<<G[v][u].to<<"是大路"<<endl;
if(d[G[v][u].to] > d[v] + G[v][u].len){
                        d[G[v][u].to] = d[v] + G[v][u].len;
                        xiaolen[G[v][u].to] = 0;
                    }
                } else {
//cout<<"到"<<G[v][u].to<<"是小路"<<endl;
long long tmp;
if(xiaolen[v] == 0){
                        tmp = G[v][u].len * G[v][u].len;
if(d[G[v][u].to] > d[v] + tmp){
                            d[G[v][u].to] = d[v] + tmp;
                            xiaolen[G[v][u].to] = G[v][u].len;
                        }
                    } else {
                        tmp = (xiaolen[v] + G[v][u].len) * (xiaolen[v] + G[v][u].len);
                        tmp -= xiaolen[v] * xiaolen[v];
if(d[G[v][u].to] > d[v] + tmp){
                            d[G[v][u].to] = d[v] + tmp;
                            xiaolen[G[v][u].to] = xiaolen[v] + G[v][u].len;
                        }
                    }
                }
            }
        }
    }


int main()
    {
scanf("%lld%lld",&n, &m);
long long t, a, b, c;
        Edge tmp;
for(long long i = 0; i < m ;i ++){
scanf("%lld%lld%lld%lld",&t, &a, &b, &c);
            tmp.type = t;
            tmp.to = b;
            tmp.len = c;
            G[a].push_back(tmp);
            tmp.to = a;
            G[b].push_back(tmp);
        }

// for(long long i = 1 ;i<=n;i++){
// for(long long j=0; j<G[i].size();j++){
// cout<<G[i][j].to<<" ";
// }
// cout<<endl;
// }

        dj();
printf("%lld\n",d[n]);

return 0;
    }
标签：

相关文章