CCF 201712-4 行车路线

目录思路DFS实现代码运行样例截图BFS实现代码目前我的程序提交只能得20分我没发现哪有问题看了好多博客下面提出的一些测试点也都能跑正确请发现问题的小伙伴跟我讨论讨论指明一下谢谢思路按深度优先搜索的思想用邻接表存储图然后遍历至尾结点n将一路上得到的疲劳度加入vector动态数组最后排序输出第一个。计算疲劳度思路通过temp[i]来记录到达 i 节点时的状态包括当前的总疲劳度、是否是经过小路到达i、如果是经过小路到达i那么连续经过了多少小路在遍历节点i的下一个节点时就把节点i的状态往下延伸从而计算得到下一个节点的状态直到遍历到n结束。DFS实现代码#includecstdio#includealgorithm#includevector#includecstringusing namespace std;constintMAXN510;typedef long long ll;struct Edge{ll d;int v,t;Edge(int _v,ll _d,int _t):v(_v),d(_d),t(_t){};};struct Node{ll allDis,allEdge;int flag;Node(){};Node(ll _allDis,ll _allEdge,int _flag):allDis(_allDis),allEdge(_allEdge),flag(_flag){};}temp[MAXN];vectorEdgeAdj[MAXN];vectorlldi;int n,m;voidDFS(int s){for(int i0;iAdj[s].size();i){int vAdj[s][i].v;ll dAdj[s][i].d;int tAdj[s][i].t;ll new_allEdge;if(t1){temp[v].allEdgetemp[s].allEdged;temp[v].allDistemp[s].allDis-temp[s].allEdge*temp[s].allEdgetemp[v].allEdge*temp[v].allEdge;temp[v].flag1;}else{temp[v].allDistemp[s].allDisd;temp[v].flag0;temp[v].allEdge0;}if(vn){di.push_back(temp[v].allDis);continue;}DFS(v);}}intmain(){int t,a,b;ll c;scanf(%d%d,n,m);for(int i0;im;i){scanf(%d%d%d%lld,t,a,b,c);Adj[a].push_back(Edge(b,c,t));}temp[1].allDis0;temp[1].allEdge0;temp[1].flag0;DFS(1);sort(di.begin(),di.end());printf(%lld,di.front());return0;}运行样例截图这是我把运行样例的每一条路径所消耗的疲劳度都打印出来了。按理输出第一个就行BFS实现代码#includecstdio#includealgorithm#includevector#includecstringusing namespace std;constintMAXN510;typedef long long ll;struct Edge{ll d;int v,t;Edge(int _v,ll _d,int _t):v(_v),d(_d),t(_t){};};struct Node{ll allDis,allEdge;int flag;Node(){};Node(ll _allDis,ll _allEdge,int _flag):allDis(_allDis),allEdge(_allEdge),flag(_flag){};};vectorNodedp[3];vectorEdgeAdj[MAXN];vectorEdgeAdj1[MAXN];vectorlldi;int n,m;ll minDis1e18;int tl;voidBFS(int s){int t21-tl;if(Adj1[s].size()0s!n)return;for(int j0;jdp[tl].size();j){Node ansdp[tl][j],temp;for(int i0;iAdj[s].size();i){int vAdj[s][i].v;ll dAdj[s][i].d;int tAdj[s][i].t;if(t1){temp.allEdgeans.allEdged;temp.allDisans.allDis-ans.allEdge*ans.allEdgetemp.allEdge*temp.allEdge;temp.flag1;}else{temp.allDisans.allDisd;temp.flag0;temp.allEdge0;}if(v1){di.push_back(temp.allDis);continue;}elsedp[t2].push_back(temp);}}dp[tl].clear();tlt2;}intmain(){int t,a,b;ll c;scanf(%d%d,n,m);for(int i0;im;i){scanf(%d%d%d%lld,t,a,b,c);Adj[b].push_back(Edge(a,c,t));Adj1[a].push_back(Edge(b,c,t));}dp[tl].push_back(Node(0,0,0));for(int in;i1;i--){BFS(i);}sort(di.begin(),di.end());printf(%lld,di.front());return0;}