参考

（参考网站的代码注释中“大路加小路”与“小路加大路”反了，网站中对spfa算法的描述很有参考价值）

思路

spfa+大路小路分开处理

实现

通过Floyd算法得出纯小路的点间最短路径，通过dis[wide][i]存储最后一条路为大路时源点到i的最短路径，dis[narrow][i]存储最后一条路为小路时源点到i的最短路径，这样spfa要考虑“大路加大路”“小路加大路”“大路加小路”三种情况。

1 #include
      
         2   3 using namespace std;  4   5 #define MAXN 505  6   7 typedef long long ll;  8   9 int n,m; 10 ll G[2][MAXN][MAXN]; 11 ll dis[2][MAXN]; 12 bool inque[MAXN]; 13 queue
       
         q; 14  15 const ll inf=1e18; 16 const int wide=0; 17 const int narrow=1; 18  19 int spfa(int start,int n){ 20     //初始化  21     for(int i=1;i<=n;i++){ 22         dis[0][i]=dis[1][i]=inf; 23         inque[i]=false; 24     } 25     //start入队  26     q.push(start); 27     inque[start]=true; 28     dis[wide][start]=dis[narrow][start]=0; 29     //spfa计算最短路径 30     int u;  31     ll v; 32     while(!q.empty()){ 33         //出队  34         u=q.front(); 35         q.pop(); 36         inque[u]=false; 37          38         for(int i=1;i<=n;i++){ 39             v=G[wide][u][i]; 40             //大路加大路 41             if(dis[wide][i]>dis[wide][u]+v){ 42                 dis[wide][i]=dis[wide][u]+v; 43                 if(!inque[i]){ 44                     q.push(i); 45                     inque[i]=true; 46                 } 47             } 48             //小路加大路 49             if(dis[wide][i]>dis[narrow][u]+v){ 50                 dis[wide][i]=dis[narrow][u]+v; 51                 if(!inque[i]){ 52                     q.push(i); 53                     inque[i]=true; 54                 } 55             } 56             //大路加小路  57             v=G[narrow][u][i]; 58             if(v!=inf&&dis[narrow][i]>dis[wide][u]+v*v){ 59                 dis[narrow][i]=dis[wide][u]+v*v; 60                 if(!inque[i]){ 61                     q.push(i); 62                     inque[i]=true; 63                 } 64             } 65         }      66     } 67     return min(dis[wide][n],dis[narrow][n]); 68 } 69  70 int main(){ 71     cin>>n; 72     cin>>m; 73     //初始化  74     for(int i=1;i<=n;i++){ 75         for(int j=1;j<=n;j++){ 76             G[0][i][j]=G[1][i][j]=inf; 77         } 78     } 79     //输入边 80     int type,u,v,w; 81     for(int i=0;i
        
         >type>>u>>v>>w; 83         if(G[type][u][v]>w){                    //注意有重边的情况  84             G[type][u][v]=G[type][v][u]=w;         85         } 86     }  87     //Floyd算法得到小边连小边的情况 88     for(int i=1;i<=n;i++){ 89         for(int j=i+1;j<=n;j++){ 90             for(int k=1;k<=n;k++){ 91                 if(k==i||k==j){ 92                     continue; 93                 } 94                 if(G[narrow][i][j]>G[narrow][i][k]+G[narrow][k][j]){ 95                     G[narrow][i][j]=G[narrow][j][i]=G[narrow][i][k]+G[narrow][k][j]; 96                 } 97             } 98         } 99     } 100     101     cout<
        
       
      

注意

有重复边输入的情况，中间结果大小可能超过int

题目

问题描述

　　小明和小芳出去乡村玩，小明负责开车，小芳来导航。

　　小芳将可能的道路分为大道和小道。大道比较好走，每走1公里小明会增加1的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走

s公里小明会增加

s

²的疲劳度。

　　例如：有5个路口，1号路口到2号路口为小道，2号路口到3号路口为小道，3号路口到4号路口为大道，4号路口到5号路口为小道，相邻路口之间的距离都是2公里。如果小明从1号路口到5号路口，则总疲劳值为(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

 

样例说明

　　从1走小道到2，再走小道到3，疲劳度为5

²=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 ≤ 10

⁵，1 ≤ 

a, 

b ≤ 

n，

t是0或1，

c

 ≤ 10

⁵。保证答案不超过10

⁶。