CCF 201712-4 行车路线

目录

• • 思路
  • DFS实现代码
  • 运行样例截图
  • BFS实现代码

目前我的程序提交只能得20分，我没发现哪有问题，看了好多博客下面提出的一些测试点也都能跑正确，请发现问题的小伙伴跟我讨论讨论指明一下，谢谢！

思路

按深度优先搜索的思想，用邻接表存储图，然后遍历至尾结点n，将一路上得到的疲劳度加入vector动态数组，最后排序输出第一个。
计算疲劳度思路，通过temp[i]来记录到达 i 节点时的状态，包括当前的总疲劳度、是否是经过小路到达i、如果是经过小路到达i那么连续经过了多少小路，在遍历节点i的下一个节点时就把节点i的状态往下延伸，从而计算得到下一个节点的状态，直到遍历到n结束。

DFS实现代码

#include<cstdio>#include<algorithm>#include<vector>#include<cstring>using namespace std;constintMAXN=510;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];vector<Edge>Adj[MAXN];vector<ll>di;int n,m;voidDFS(int s){for(int i=0;i<Adj[s].size();i++){int v=Adj[s][i].v;ll d=Adj[s][i].d;int t=Adj[s][i].t;ll new_allEdge;if(t==1){temp[v].allEdge=temp[s].allEdge+d;temp[v].allDis=temp[s].allDis-temp[s].allEdge*temp[s].allEdge+temp[v].allEdge*temp[v].allEdge;temp[v].flag=1;}else{temp[v].allDis=temp[s].allDis+d;temp[v].flag=0;temp[v].allEdge=0;}if(v==n){di.push_back(temp[v].allDis);continue;}DFS(v);}}intmain(){int t,a,b;ll c;scanf("%d%d",&n,&m);for(int i=0;i<m;i++){scanf("%d%d%d%lld",&t,&a,&b,&c);Adj[a].push_back(Edge(b,c,t));}temp[1].allDis=0;temp[1].allEdge=0;temp[1].flag=0;DFS(1);sort(di.begin(),di.end());printf("%lld",di.front());return0;}

运行样例截图

这是我把运行样例的每一条路径所消耗的疲劳度都打印出来了。（按理输出第一个就行）

BFS实现代码

#include<cstdio>#include<algorithm>#include<vector>#include<cstring>using namespace std;constintMAXN=510;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){};};vector<Node>dp[3];vector<Edge>Adj[MAXN];vector<Edge>Adj1[MAXN];vector<ll>di;int n,m;ll minDis=1e18;int tl;voidBFS(int s){int t2=1-tl;if(Adj1[s].size()==0&&s!=n)return;for(int j=0;j<dp[tl].size();j++){Node ans=dp[tl][j],temp;for(int i=0;i<Adj[s].size();i++){int v=Adj[s][i].v;ll d=Adj[s][i].d;int t=Adj[s][i].t;if(t==1){temp.allEdge=ans.allEdge+d;temp.allDis=ans.allDis-ans.allEdge*ans.allEdge+temp.allEdge*temp.allEdge;temp.flag=1;}else{temp.allDis=ans.allDis+d;temp.flag=0;temp.allEdge=0;}if(v==1){di.push_back(temp.allDis);continue;}elsedp[t2].push_back(temp);}}dp[tl].clear();tl=t2;}intmain(){int t,a,b;ll c;scanf("%d%d",&n,&m);for(int i=0;i<m;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 i=n;i>=1;i--){BFS(i);}sort(di.begin(),di.end());printf("%lld",di.front());return0;}``