题解 P1807 【最长路_NOI导刊2010提高（07）】

_自动AC机_ · 2018-10-28 21:19:35 · 题解

主要思路

• 这题用Floyd可以轻松A。其实就是把输入进去的边长前面加上个负号，最后输出的时候再加一次负号就行了。

主要坑点

• 最坑的就是输入数据里两个点之间可能有很多条边，我们要取合适的那条塞入邻接矩阵。（否则只能拿45分）

• 编号是从1到n的，注意处理数组越界问题。

注意事项

• 不开氧气（O2优化）可能会TLE，我没试过。（你们可以试试）

上代码

#include <iostream>
#include <cstdio>
#include <cmath>
#define INF 0x7fffffff   //手动定义INF
using namespace std;
int n,m,x,y,z,map[1501][1501];    //邻接矩阵真好玩
int main(){
    cin>>n>>m;   //输入点数和边数
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(i==j) map[i][j]=0;    //邻接矩阵赋初值
            else map[i][j]=INF;    
    for(int i=0;i<m;i++){
        cin>>x>>y>>z;
        x--,y--;   //编号从1~n，注意处理数组越界问题
        map[x][y]=min(map[x][y],-z);   //当两个点有多条路时取最长的那条
    }
    for(int k=0;k<n;k++)   //Floyd模板
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                if(map[i][k]!=INF&&map[k][j]!=INF)
                    map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
    if(map[0][n-1]==INF) cout<<-1;   //判断两个点是否连通
    else cout<<-map[0][n-1];  //相当于map[0][n-1]*-1
}

如果对您有帮助的话请点个赞哦~