• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

P1294 高手去散步 (基础模板)(DFS,搜索最长路的模板,也可以改成搜索最短路)

开发技术 开发技术 7天前 5次浏览
#include <iostream>
#include <set>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#define ll long long
using namespace std;
const int M = 1e3 + 1;
int a[M][M];//存储距离
int b[M];//存储这个点是否走过,一维数组就好,没必要用二维的数组
int n, m;
int ans = 0;

inline void dfs(int x,int s) {//x代表现在到了哪一个点,s代表现在的总路程
    ans=max(ans,s);//每次都更新一下
    for(int i=1;i<=n;i++){
        if(a[x][i]>0&&b[i]==0){//如果这个点和另外一个点存在路,因为存在路就距离一定大于0,一下子排除了很多种不符合的情况
        //同时这个景点我没走过 b[i]=1; dfs(i,s+a[x][i]);//路程+放在里面,路程就不用回溯了 b[i]=0;//回溯 } } } int main() { cin >> n >> m; while (m--) { int q1, q2, q3; cin >> q1 >> q2 >> q3; a[q1][q2] = q3; a[q2][q1] = q3; } int ma=0; for (int i = 1; i <= n; i++) { b[i]=1;//表示这个点已经走过 dfs(i,0); ma=max(ans,ma);//求出最大的 memset(b, 0, sizeof(b)); } cout << ans << endl; }

 


喜欢 (0)