#include <iostream> #include <algorithm> #include <vector> using namespace std; typedef long long ll; struct node{ int a,b,c; }; vector<node> ve; vector<int> h[101010]; int n,m; int ct=1,tm=0; int tct=101,ttm=101; void add(int x,int y,int z){ ve.push_back({x,y,z}); h[x].push_back(ve.size()-1); } //最少需要经过多少个城市 需要花费的最少时间 void dfs(int x,int fu){ if(x==n){ if(ct<tct){ tct=ct; ttm=tm; } if(ct<=tct){ if(tm<ttm){ tct=ct; ttm=tm; } } return ; } for(int i=0;i<h[x].size();i++){ int j=h[x][i]; int ne=ve[j].b; int t=ve[j].c; if(ne==fu) continue; ct++; tm+=t; dfs(ne,x); ct--; tm-=t; } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x,y,z; cin>>x>>y>>z; add(x,y,z); add(y,x,z); } dfs(1,0); ve.clear(); h[101010].clear(); cout<<tct<<" "<<ttm; return 0; }
全部评论
(1) 回帖