题目链接： 一如既往的没有啊 老哥
题目描述： 给以一个有向图， 每个边上有权值， 问你一条通路的最大权值是多少
解题思路： 这道题应该很裸吧,......自己记得以前做过啊, 自己写崩了， 明天早起去看看紫书， 那里我记得是有的啊
代码： 刚才自己总算调出来了， 自己写过的东西怎么忘得这么快啊......
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #include <map> #include <set> #include <queue> #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("======= ") typedef long long ll; using namespace std; const ll t = 1e8; const int maxn = 1e4+100; map<pair<int, int>, 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 ", ans ); } return 0; }
思考： 记性太差啦， 以后得每天一道数据结构了， 毕竟数据结构太重要了， 今天是不是又没写面试总结啊......... 然后自己关于这个程序是怎么写的还是有疑问的， 明天参照紫书， 然后自己仔细看看自己的程序， 别不长记性。