概要
问题描述
小明和小芳出去乡村玩，小明负责开车，小芳来导航。
小芳将可能的道路分为大道和小道。大道比较好走，每走1公里小明会增加1的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走s公里小明会增加s2的疲劳度。
例如：有5个路口，1号路口到2号路口为小道，2号路口到3号路口为小道，3号路口到4号路口为大道，4号路口到5号路口为小道，相邻路口之间的距离都是2公里。如果小明从1号路口到5号路口，则总疲劳值为(2+2)2+2+22=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
样例说明
从1走小道到2，再走小道到3，疲劳度为52=25；然后从3走大道经过4到达5，疲劳度为20+30=50；最后从5走小道到6，疲劳度为1。总共为76。
数据规模和约定
对于30%的评测用例，1 ≤ n ≤ 8，1 ≤ m ≤ 10；
对于另外20%的评测用例，不存在小道；
对于另外20%的评测用例，所有的小道不相交；
对于所有评测用例，1 ≤ n ≤ 500，1 ≤ m ≤ 105，1 ≤ a, b ≤ n，t是0或1，c ≤ 105。保证答案不超过106。
思路
该题有大路与小路的区别，同时对于小路还有是否连续之说。主要思路是，将大路与小路的款邻接矩阵分开进行存储。在执行迪杰斯特拉算法时，没找到一个顶点时，设置f标志位lag，若为1则前驱为小路，若为0则为大路。对距离数组进行更新时，分别对小路与大路进行判断跟新。
AC代码
1#include <iostream> 2#include <string.h> 3#include <cmath> 4#include <vector> 5#include <cstdio> 6using namespace std; 7 8typedef long long ll; 9const ll INF = 0x7fffffffffffffff; 10ll sA[512][512]; //小路的邻接矩阵 11ll bA[512][512]; //大路的邻接矩阵 12int isvisited_sr[512]; //小路访问数组 13int isvisited_br[512]; //大路访问数组 14ll n,m; 15ll ans; //结果 16 17//平方函数 18ll Pow2(ll a) 19{ 20 return a*a; 21} 22 23 24/* 迪杰斯特拉算法 25 该题把大路和小路分开判断 26*/ 27ll Dijikstra(ll t) 28{ 29 vector<ll> sr(sA[t],sA[t]+n); //第i结点小路的距离矩阵 30 vector<ll> br(bA[t],bA[t]+n); //第i结点大路的距离矩阵 31 vector<ll> pre_sr(n,INF); //第i结点小路的邻接矩阵 32 for(int i = 0 ; i < n ; i++){ 33 if(sr[i] < INF){ 34 pre_sr[i] = sr[i]; 35 sr[i] *= sr[i]; 36 } 37 } 38 isvisited_br[t] = isvisited_sr[t] = 1; 39 while(1){ 40 ll MinVal = INF,flag = 0,v = -1; 41 for(int i = 0 ; i < n ; i++){ 42 if(!isvisited_br[i] && br[i] < MinVal){ 43 44 45 //大路 46 flag = 0; 47 MinVal = br[v=i]; 48 } 49 if(!isvisited_sr[i] && sr[i] < MinVal){ 50 51 52 //小路 53 flag = 1; 54 MinVal = sr[v=i]; 55 } 56 } 57 if(v == -1){ 58 break; 59 } 60 if(flag == 1){ 61 62 63 //大路 64 isvisited_sr[v] = 1; 65 }else{ 66 67 68 //小路 69 isvisited_br[v] = 1; 70 } 71 for(int i = 0 ; i < n ; i++){ 72 if(isvisited_sr[i] == 0 && sA[v][i] < INF){ 73 74 75 //v到i存在一条小路 76 if(flag == 1){ 77 78 79 //v的前驱是小路 80 ll len = sr[v] - Pow2(pre_sr[v]) + Pow2(pre_sr[v]+sA[v][i]); 81 if(sr[i] > len || (sr[i] == len && pre_sr[i] > pre_sr[v]+sA[v][i])){ 82 sr[i] = len; 83 pre_sr[i] = pre_sr[v]+sA[v][i]; 84 } 85 }else{ 86 87 88 //v的前驱是大路 89 ll len = br[v]+ Pow2(sA[v][i]); 90 if(sr[i] > len || (sr[i] == len && pre_sr[i] > sA[v][i])){ 91 sr[i] = len; 92 pre_sr[i] = sA[v][i]; 93 } 94 } 95 } 96 if(isvisited_br[i] == 0 && bA[v][i] < INF){ 97 98 99 //v到i存在一条大路 100 if(flag == 1){ 101 102 103 //v的前驱是小路 104 ll len = sr[v] + bA[v][i]; 105 br[i] = min(len,br[i]); 106 }else{ 107 108 109 //v的前驱是大路 110 ll len = br[v] + bA[v][i]; 111 br[i] = min(br[i],len); 112 } 113 } 114 } 115 } 116 return min(sr[n-1],br[n-1]); 117} 118 119int main() 120{ 121 while(cin>>n>>m){ 122 //对数组进行初始化 123 for(int i = 0 ; i < n ; i++){ 124 for(int j = 0 ; j < n ; j++){ 125 sA[i][j] = sA[j][i] = INF; 126 bA[i][j] = bA[j][i] = INF; 127 } 128 } 129 130 for(int i = 0 ; i < 512 ; i++){ 131 isvisited_sr[i] = isvisited_br[i] = 0; 132 } 133 134 //数据输入，对图进行初始化 135 for(int i = 0 ; i < m ; i++){ 136 ll t,a,b,c; 137 cin>>t>>a>>b>>c; 138 a--,b--; 139 if(t == 1){ 140 sA[a][b] = sA[b][a] = min(c,sA[a][b]); 141 }else{ 142 bA[a][b] = bA[b][a] = min(c,bA[a][b]); 143 } 144 } 145 ans = Dijikstra(0); 146 printf("%lld\n",ans); 147 } 148 149 return 0; 150}
本文分享 CSDN - 追梦者_AIer。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。