- 题目描写叙述：
- 给你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 21 2 5 62 3 4 51 30 0
- 例子输出：
-
9 11
题目比較简单 用邻接矩阵+Dijkstra就可以
#include#include using namespace std;int data[1001][1001][2];int dis[1001];int fare[1001];int points[1001];bool isOver(int points[],int n){ bool over = true; for(int i = 1; i <= n; i++){ if(points[i] == 0){ over = false; break; } } return over;}int main(){ int n,m; scanf("%d %d",&n,&m); while(n != 0 && m != 0){ for(int i = 0; i < 1001;i++){//初始化 for(int j = 0; j < 1001;j++){ data[i][j][0] = -1; data[i][j][1] = -1; } dis[i] = -1; fare[i] = -1; points[i] = 0; } for(int i = 0; i < m; i++){//读数据 int point1,point2,distance,money; scanf("%d %d %d %d",&point1,&point2,&distance,&money); data[point1][point2][0] = distance; data[point1][point2][1] = money; data[point2][point1][0] = distance; data[point2][point1][1] = money; } int beginp,endp; scanf("%d %d",&beginp,&endp); dis[beginp] = 0; fare[beginp] = 0; points[beginp] = 1; for(int i = 1; i <= n; i++){ if(data[beginp][i][0] != -1){ dis[i] = data[beginp][i][0]; fare[i] = data[beginp][i][1]; } } while(!isOver(points,n)){ int point = -1,anotherP= -1,minMoney,minDis = -1; for(int i = 1; i <= n;i++){ if(points[i]==1){//已确定点 for(int j = 1; j <= n; j++){ if(points[j] == 0){//未确定点 if(data[i][j][0] ==-1) continue; if(minDis == -1 || minDis > data[i][j][0]){ minDis = data[i][j][0]; minMoney = data[i][j][1]+fare[i]; point = j; anotherP = i; }else if(minDis == data[i][j][0] && (fare[anotherP] + data[anotherP][point][1] > fare[i] + data[i][j][1])){//距离同样比較花费 minDis = data[i][j][0]; minMoney = data[i][j][1]; point = j; anotherP = i; } } } } } // points[point] = 1; dis[point] = dis[anotherP]+ data[anotherP][point][0]; fare[point] = fare[anotherP] + data[anotherP][point][1]; for(int i = 1; i <= n ;i++){ if(points[i] == 0 &&data[point][i][0] != -1){ if(dis[i] == -1 || dis[i] > dis[point] +data[point][i][0]){ dis[i] = dis[point] + data[point][i][0]; } } } } printf("%d %d\n",dis[endp],fare[endp]); scanf("%d %d",&n,&m); } return 0;}