浙江大学10年计算机上机题（含答案）

m为0时输入结束。

(1

输出：

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

样例输入： 3 2

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

样例输出： 9 11

答案：

题目距离d和花费p没有给出取值范围，所以在初始化的时候表示最大距离和花费的无穷大用（-1）或者设置尽可能大的数。

下面是代码，思想很简单就是邻接矩阵存储，然后在dijkstra算法上增加花费条件判断。

1. 2. 3. 4. 5. 6. 7. 8. 9.

#include #define N 1001 #define MAX 100000000 #define INF 1000000000 typedef struct{ int dist;

int expend; }edge;

edge arcs[N][N];

10. int start,end,n,m; 11. void dijkstra(){ 12. int s[n]; 13. edge d[n]; 14. int i,j,k,v; 15. int min; 16. v = start - 1;

17. for(i = 0; i < n; i ++){ 18. d[i] = arcs[v][i]; 19. }

20. for(i = 0; i < n; i ++) s[i] = 0; 21. s[v] = 1; d[v].dist = 0; d[v].expend = 0; 22. for(i = 0; i < n-1; i ++){ 23. min = INF;

24. for(j = 0;j < n;j ++)

25. if((s[j] == 0) && (d[j].dist >= 0) && (d[j].dist < min)){ 26. min = d[j].dist; 27. k = j; 28. }

29. s[k] = 1;

30. for(j = 0;j < n; j ++){

31. if((s[j] == 0) && (d[j].dist > d[k].dist +

arcs[k][j].dist)){

32. d[j].dist = d[k].dist + arcs[k][j].dist; 33. d[j].expend = arcs[k][j].expend + d[k].expend; 34. }

35. else if((s[j] == 0) && (d[j].dist == d[k].dist +

arcs[k][j].dist)){

36. if(d[j].expend > arcs[k][j].expend + d[k].expend) 37. d[j].expend = arcs[k][j].expend + d[k].expend; 38. } 39. } 40. }

41. printf(\42. }

43. int main(){

44. int s,t,d,p; 45. int i,j;

46. while(scanf(\

47. if(n == 0 && m == 0) return 0; 48. for(i = 0;i < n;i ++){

49. for(j = 0;j < n;j ++){

50. arcs[i][j].dist = MAX; 51. arcs[i][j].expend = MAX; 52. } 53. }

54. for(i = 0;i < m; i ++){

55. scanf(\56. arcs[s-1][t-1].dist = d; 57. arcs[t-1][s-1].dist = d; 58. arcs[s-1][t-1].expend = p; 59. arcs[t-1][s-1].expend = p; 60. }

61. scanf(\62. dijkstra(); 63. }

64. return 0; 65. }

邻接表 + Dijstra + 优先队列，效率应该比较可以，果断AC！

1. 2. 3. 4. 5. 6. 7. 8. 9.

#include #include #include // #include #include #include #include #include using namespace std;

10.

11. #define INF (1<<30) 12. #define MAXM 100002 13. #define MAXN 1002 14.

15. typedef struct Tab{ 16. int eid;

17. struct Tab *next; 18. Tab()://构造函数

19. eid(-1),next(NULL){} 20. }tab; 21.

22. int u[MAXM], v[MAXM], d[MAXM], p[MAXM]; 23. int n, m; 24. int s, t; 25.

26. typedef pair pii;

27. priority_queue, greater > PQ; 28.

29. bool vis[MAXN]; 30. int dis[MAXN]; 31. int val[MAXN]; 32.

33. int main() 34. {

35. //freopen(\36. while(scanf(\37. {

38. tab first[MAXN];//构造函数已经初始化了，不需要再次初始化 39. //read_graph

40. for(int e=1; e<=m; e++) 41. {

42. scanf(\