题解 P2559 【[AHOI2002]哈利·波特与魔法石】

· · 题解

这是绿名蒟蒻第二次发题解（第一次没有通过）......

一道相对简单的省选题（最短路模板题）也是我AC的第一道绿题

每两个城市之间的时间由地形和有无魔法石决定，而每个地形通过的时间是固定的（2,6,4,8,6,10,14），输入了魔法石的有无，所以时间就出来了。

众所周知，最短路算法很多，这里我选用了Floyd算法（时复N^3），我觉得比较好懂，代码也简单（城市编号不超过100，这不是明显暗示用Floyd吗）反正我连Dijkstra都不会

以下是Floyd具体思路：

用dis[i][j]数组表示i~j的最短路径，从1~n枚举中间点k，如果从i到j过k有更短的路径就刷新，否则保留原来路径（有点动规思想，转移方程：dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])）

注意事项： 1 循环时要把中间点k放在最外层； 2 一开始时（输入前）每两个点之间都是没有路的，所以距离要标成无限而不是0，否则会导致所有点之间的距离都是0 3 这种算法只适用于无负环图（也就是不存在边权值和＜0的环）不过好像和这题没有关系

献上码风奇特的代码（有一些注释，不过我语文不太好，还请见谅）

#include <bits/stdc++.h>
using namespace std;
unsigned long long i,j,k,x,y,c,dist[105][105];//这个数组记录距离 
int s[8]={99999,2,6,4,8,6,10,14};//这个数组记录每个地形花费时间(我习惯从1开始,所以s[0]要空出) 
bool ck[8];//判断有没有石头 
int main(){
    memset(dis,100000,sizeof(dis));//初始化:必须足够大(即一开始最短路是无限长) 
    for(i=1;i<8;i++)cin>>ck[i]; 
    cin>>x>>y>>c;//x起点,y终点(我更习惯用变量i,j写for循环) 
    if(x==y){ //特判:如果x,y相等就是0!!!!(第一次提交WA了9号点,就因为这个) 
        cout<<0;
        return 0;
    }
    while(c--){
        cin>>i>>j>>k;
        if(ck[k]){ //有石头,花费减半 
            dis[i][j]=s[k]/2;
            dis[j][i]=s[k]/2;//注意这里是双向边,所以两头都要记录    
        }
        else { //没石头,花费照常 
            dis[i][j]=s[k];
            dis[j][i]=s[k];
        }
    }
    for(k=1;k<=100;k++){ //Floyd核心代码,具体思路见上(注意中间点循环放最外层) 
        for(i=1;i<=100;i++){
            for(j=1;j<=100;j++){
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    cout<<dis[x][y]<<endl;//最后输出从x到y最短路距离 
    return 0;
}