2025年浙江大学计算机考研复试机试真题（附 AC 代码 + 解题思路）

2025年浙江大学计算机考研复试机试真题

2025年浙江大学计算机考研复试上机真题

历年浙江大学计算机考研复试上机真题

历年浙江大学计算机考研复试机试真题

更多学校题目开源地址：https://gitcode.com/verticallimit1/noobdream

N 诺 DreamJudge 题库：输入 “学校名称” 即可筛选该校历年机试真题，题目均在考纲范围内，按难度自动排序。还可搭配《计算机考研机试攻略》刷题，书中题目可通过题号直接在题库中查找。

最短路径问题

题目描述

Time Limit: 1000 ms
Memory Limit: 256 mb

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

输入输出格式

输入描述:

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。 (1<n<=1000, 0<m<100000, s != t)

输出描述:

输出 一行有两个数， 最短距离及其花费。

输入输出样例

输入样例#:

3 2 1 2 5 6 2 3 4 5 1 3 0 0

输出样例#:

9 11

代码一

1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. #include <iomanip>
5. #include <set>
6. #include <list>
7. #include <string>
8. #include <cmath>
9. #include <stack>
10. #include <map>
11. #include <sstream>
12. #include <queue>
13. using namespace std;
14. struct edge {
15. int target;
16. int length;
17. int cost;
18. };
19. vector<int>dist;
20. vector<int>cost;
21. struct compare_dist {
22. bool operator()(int& a, int& b) {
23. return dist[a] > dist[b];
24. }
25. };
26. int main() {
27. int n, m;
28. while (cin >> n >> m) {
29. if (n == 0)break;
30. map<int, vector<edge>>graph;
31. dist.resize(n + 1); cost.resize(n + 1);
32. for (int i = 1; i <= n; i++) {
33. dist[i] = 1e9;
34. cost[i] = 1e9;
35. }
36. int node1, node2, length3, cost3;
37. for (int i = 0; i < m; i++) {
38. cin >> node1 >> node2 >> length3 >> cost3;
39. edge temp; temp.target = node2; temp.cost = cost3; temp.length = length3;
40. graph[node1].push_back(temp);
41. temp.target = node1;
42. graph[node2].push_back(temp);
43. }
44. int s, t;
45. cin >> s >> t;
46. dist[s] = 0; cost[s] = 0;
47. priority_queue<int, vector<int>, compare_dist>pq;
48. pq.push(s);
49. while (!pq.empty()) {
50. int curr_node = pq.top(); pq.pop();
51. if (curr_node == t)break;
52. if(!graph[curr_node].empty()){
53. for (auto v : graph[curr_node]) {
54. int new_dist = dist[curr_node] + v.length;
55. int new_cost = cost[curr_node] + v.cost;
56. if (new_dist < dist[v.target]) {
57. dist[v.target] = new_dist;
58. cost[v.target] = new_cost;
59. pq.push(v.target);
60. }
61. else if (new_dist == dist[v.target] && new_cost < cost[v.target]) {
62. cost[v.target] = new_cost;
63. pq.push(v.target);
64. }
65. }
66. }
67. }
68. cout << dist[t] << ' ' << cost[t] << endl;
69. }
70. return 0;
71. }

代码二

1. #include <iostream>
2. #include <vector>
3. #include <queue>
4. using namespace std;
5. struct Edge{
6. int x,y,d,p;
7. };
8. struct Node{
9. int x,d,p;
10. friend bool operator <(Node a, Node b){
11. if(a.d == b.d) return a.p > b.p;
12. return a.d > b.d;
13. }
14. };
15. const int maxN = 1000;
16. const int INF = 0x3f3f3f3f;
17. vector<int> e[maxN+5];
18. vector<Edge> edges;
19. int dis[maxN+5];
20. int prices[maxN+5];
21. bool vis[maxN+5];
22. void addEdge(int a, int b, int d, int p){
23. e[a].push_back(edges.size());
24. edges.push_back({a,b,d,p});
25. }
26. int dijkstra(int s){
27. dis[s] = 0;
28. prices[s] = 0;
29. priority_queue<Node> pq;
30. pq.push({s,0,0});
31. while(!pq.empty()){
32. Node now = pq.top();
33. vis[now.x] = true;
34. pq.pop();
35. for(int i = 0; i < e[now.x].size(); i++){
36. Edge edge = edges[e[now.x][i]];
37. if(dis[edge.y] > dis[edge.x]+edge.d
38. || dis[edge.y] == dis[edge.x]+edge.d
39. && prices[edge.y] > prices[edge.x]+edge.p){
40. dis[edge.y] = dis[edge.x]+edge.d;
41. prices[edge.y] = prices[edge.x]+edge.p;
42. pq.push({edge.y, dis[edge.y],prices[edge.y]});
43. }
44. }
45. }
46. return 0;
47. }
48. int main() {
49. int n,m;
50. int a,b,d,p;
51. int s, t;
52. while(cin >> n >> m){
53. if(n == 0 && m == 0)break;
54. for(int i = 1; i <= n; i++){
55. dis[i] = INF;
56. prices[i] = INF;
57. }
58. for(int i = 0; i < m; i++){
59. cin >> a >> b >> d >> p;
60. addEdge(a,b,d,p);
61. addEdge(b,a,d,p);
62. }
63. cin >> s >> t;
64. dijkstra(s);
65. cout << dis[t] << " " << prices[t] << endl;
66. }
67. return 0;
68. }

代码三

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int INF = 0x3f3f3f3f;
4. int n,m;
5. const int maxn = 1001;
6. struct edge {
7. int u,v,w,p;
8. edge(int _u, int _v, int _w,int _p) : u(_u), v(_v), w(_w), p(_p){}
9. };
10. vector<edge> edges;
11. vector<int> G[maxn];//每个点的边在edges中的下标
12. int vis[maxn];
13. int dist[maxn];
14. int path[maxn];
15. int cost[maxn]; //从起点到某个点i的最少花费cost[i],但是是在距离最短优先情况下
16. void spfa(int s) {
17. queue<int> q;
18. q.push(s);
19. for(int i = 0; i <= n; i++) {
20. dist[i] = INF;
21. }
22. dist[s] = 0;
23. memset(cost,0,sizeof(cost));
24. memset(vis,0,sizeof(vis));
25. while(!q.empty()) {
26. int u = q.front();
27. q.pop();
28. vis[u] = 0;
29. for(int i = 0; i < G[u].size(); i++) {
30. edge e = edges[G[u][i]];
31. if(dist[e.v] > dist[u] + e.w) {
32. dist[e.v] = dist[u] + e.w;
33. path[e.v] = u;
34. cost[e.v] = cost[u] + e.p;
35. if(vis[e.v] == 0) {
36. q.push(e.v);
37. vis[e.v] = 1;
38. }
39. }else if(dist[e.v] == dist[u] + e.w) {
40. int new_cost = cost[e.u] + e.p;
41. if(new_cost < cost[e.v]) {
42. cost[e.v] = new_cost;
43. path[e.v] = u;
44. }
45. }
46. }
47. }
48. }
49. void addedge(int a, int b,int c, int d) {
50. edges.push_back(edge(a,b,c,d));
51. G[a].push_back(edges.size()-1);
52. }
53. void init() {
54. for(int i = 0; i <= n ;i++) G[i].clear();
55. edges.clear();
56. }
57. int main() {
58. while(cin>>n>>m) {
59. if(n == 0 && m == 0) break;
60. init();
61. int a,b,c,d;
62. for(int i=0;i<m;i++) {
63. cin>>a>>b>>c>>d;
64. addedge(a,b,c,d);
65. addedge(b,a,c,d);
66. }
67. int s,t;
68. cin >> s >> t;
69. spfa(s);
70. cout<< dist[t] << ' ' << cost[t] << endl;
71. }
72. }