题目链接：1724 -- ROADS
题面：
题意：有r条单向道路,每条路有一个过路费和时间，我只有k元，问走到n的最少时间
思路：用链式前向星存图，然后搜索遍历一遍。
两个剪枝：
1.如果花费超过k了直接返回。
2.如果走到某个点的时间超过最短时间就返回
#include #include #include #include #include #include #include #include #include #include using namespace std; #define endl "n" #define pi pair #define ll long long #define N 105 #define M 20005 int minn; bool vis[105]; int h[N], to[M], nex[M], w[M], s[M]; int cnt; void add(int u, int v, int a, int b){ to[cnt] = v; nex[cnt] = h[u]; w[cnt] = a; s[cnt] = b; h[u] = cnt++; } void dfs(int x, int n, int d, int l, int k){ if(d > k){ return ; } if(l >= minn){ return ; } if(x == n){ minn = min(minn, l); return ; } vis[x] = 1; for(int i = h[x]; i != -1; i = nex[i]){ int v = to[i]; if(vis[v] == 0){ dfs(v, n, d + s[i], l + w[i], k); } } vis[x] = 0; } int main(){ ios::sync_with_stdio(false); int k, n, r; while(cin >> k >> n >> r){ for(int i = 1; i <= n; i++){ vis[i] = 0; h[i] = -1; } cnt = 0; for(int i = 0; i < r; i++){ int a, b, c, d; cin >> a >> b >> c >> d; add(a, b, c, d); } minn = 2147483647; dfs(1, n, 0, 0, k); if(minn == 2147483647){ cout << -1 << endl; }else{ cout << minn << endl; } } return 0; }
上一篇 浅谈2022Android岗面试趋势，什么有必要学？
下一篇 三面头条，靠P9级算法分享的两本算法pdf书籍，轻松拿到offer
版权所有 (c)2021-2022 MSHXW.COM
ICP备案号：晋ICP备2021003244-6号
