CCF考试——201712-4行车路线
概要
问题描述
小明和小芳出去乡村玩，小明负责开车，小芳来导航。 小芳将可能的道路分为大道和小道。大道比较好走，每走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代码
#include <iostream>
#include <string.h>
#include <cmath>
#include <vector>
#include <cstdio>
using namespace std;
typedef long long ll;
const ll INF = 0x7fffffffffffffff;
ll sA[512][512]; //小路的邻接矩阵
ll bA[512][512]; //大路的邻接矩阵
int isvisited_sr[512]; //小路访问数组
int isvisited_br[512]; //大路访问数组
ll n,m;
ll ans; //结果
//平方函数
ll Pow2(ll a)
{
return a*a;
}
/* 迪杰斯特拉算法
该题把大路和小路分开判断
*/
ll Dijikstra(ll t)
{
vector<ll> sr(sA[t],sA[t]+n); //第i结点小路的距离矩阵
vector<ll> br(bA[t],bA[t]+n); //第i结点大路的距离矩阵
vector<ll> pre_sr(n,INF); //第i结点小路的邻接矩阵
for(int i = 0 ; i < n ; i++){
if(sr[i] < INF){
pre_sr[i] = sr[i];
sr[i] *= sr[i];
}
}
isvisited_br[t] = isvisited_sr[t] = 1;
while(1){
ll MinVal = INF,flag = 0,v = -1;
for(int i = 0 ; i < n ; i++){
if(!isvisited_br[i] && br[i] < MinVal){//大路
flag = 0;
MinVal = br[v=i];
}
if(!isvisited_sr[i] && sr[i] < MinVal){//小路
flag = 1;
MinVal = sr[v=i];
}
}
if(v == -1){
break;
}
if(flag == 1){//大路
isvisited_sr[v] = 1;
}else{//小路
isvisited_br[v] = 1;
}
for(int i = 0 ; i < n ; i++){
if(isvisited_sr[i] == 0 && sA[v][i] < INF){//v到i存在一条小路
if(flag == 1){//v的前驱是小路
ll len = sr[v] - Pow2(pre_sr[v]) + Pow2(pre_sr[v]+sA[v][i]);
if(sr[i] > len || (sr[i] == len && pre_sr[i] > pre_sr[v]+sA[v][i])){
sr[i] = len;
pre_sr[i] = pre_sr[v]+sA[v][i];
}
}else{//v的前驱是大路
ll len = br[v]+ Pow2(sA[v][i]);
if(sr[i] > len || (sr[i] == len && pre_sr[i] > sA[v][i])){
sr[i] = len;
pre_sr[i] = sA[v][i];
}
}
}
if(isvisited_br[i] == 0 && bA[v][i] < INF){//v到i存在一条大路
if(flag == 1){//v的前驱是小路
ll len = sr[v] + bA[v][i];
br[i] = min(len,br[i]);
}else{//v的前驱是大路
ll len = br[v] + bA[v][i];
br[i] = min(br[i],len);
}
}
}
}
return min(sr[n-1],br[n-1]);
}
int main()
{
while(cin>>n>>m){
//对数组进行初始化
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
sA[i][j] = sA[j][i] = INF;
bA[i][j] = bA[j][i] = INF;
}
}
for(int i = 0 ; i < 512 ; i++){
isvisited_sr[i] = isvisited_br[i] = 0;
}
//数据输入，对图进行初始化
for(int i = 0 ; i < m ; i++){
ll t,a,b,c;
cin>>t>>a>>b>>c;
a--,b--;
if(t == 1){
sA[a][b] = sA[b][a] = min(c,sA[a][b]);
}else{
bA[a][b] = bA[b][a] = min(c,bA[a][b]);
}
}
ans = Dijikstra(0);
printf("%lld\n",ans);
}
return 0;
}