本文共 1513 字，大约阅读时间需要 5 分钟。
题目链接： 一如既往的没有啊 老哥
题目描述： 给以一个有向图， 每个边上有权值， 问你一条通路的最大权值是多少
解题思路： 这道题应该很裸吧,......自己记得以前做过啊, 自己写崩了， 明天早起去看看紫书， 那里我记得是有的啊
代码： 刚才自己总算调出来了， 自己写过的东西怎么忘得这么快啊......
#include #include #include #include #include #include #include #include #include #include #include #include #include #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1#define mem0(a) memset(a,0,sizeof(a))#define mem1(a) memset(a,-1,sizeof(a))#define sca(x) scanf("%d",&x)#define de printf("=======\n")typedef long long ll;using namespace std;const ll t = 1e8;const int maxn = 1e4+100;map , int> p;int d[maxn]; // d[i] 表示i号节点为起点的最长距离为d[i]int isend[maxn];int n, m;int dfs( int index ) { if( isend[index] ) return 0; for( int i = 1; i <= n; i++ ) { if( i != index ) { int dis = p[make_pair(index, i)]; if( dis ) { d[index] = max( d[index], dis + dfs(i) ); } } } return d[index];}int main() { int t; sca(t); while( t-- ) { scanf( "%d%d", &n, &m ); p.clear(); mem0(d); mem0(isend); for( int i = 1; i <= m; i++ ) { int s, e, l; scanf( "%d%d%d", &s, &e, &l ); p.insert(make_pair(make_pair(s, e), l)); isend[s] = 0; isend[e] = 1; } int ans = 0; for( int i = 1; i <= n; i++ ) { ans = max( ans, dfs(i) ); } printf( "%d\n", ans ); } return 0;}
思考： 记性太差啦， 以后得每天一道数据结构了， 毕竟数据结构太重要了， 今天是不是又没写面试总结啊......... 然后自己关于这个程序是怎么写的还是有疑问的， 明天参照紫书， 然后自己仔细看看自己的程序， 别不长记性。
转载于:https://www.cnblogs.com/FriskyPuppy/p/7499869.html
