P205 最短路径问题

错误，最少花费比实际少
#include

using namespace std;

const int N = 1000;
const int INF = 10000000;

int n, m, s, t;
int length[N][N];
int price[N][N];
int dis[N];
int cost[N];
int vis[N];

void init(){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
length[i][j] = INF;
price[i][j] = INF;
}
}
}

void Djikstra(int s){
int i, j;
for(i = 1; i <= n; i++){
dis[i] = length[s][i];
cost[i] = price[s][i];
vis[i] = 0;
}
dis[s] = 0;
cost[s] = 0;
vis[s] = 1;
int mindis, mincost, minnode;
for(i = 1; i <= n; i++){
mindis = mincost = INF;
minnode = 0;
for(j = 1; j <= n; j++){
if(!vis[j] && mindis == dis[j]){
if(mincost > cost[j]){
minnode = j;
mincost = cost[j];
}
}
if(!vis[j] && mindis > dis[j]){
minnode = j;
mindis = dis[j];
}
}
if(mindis == INF) break;
vis[minnode] = 1;
for(j = 1; j <= n; j++){
if(!vis[j] && dis[j] == dis[minnode] + length[minnode][j]){
if(cost[j] > cost[minnode] + price[minnode][j]){
cost[j] = cost[minnode] + price[minnode][j];
}
}
if(!vis[j] && dis[j] > dis[minnode] + length[minnode][j]){
dis[j] = dis[minnode] + length[minnode][j];
cost[j] = cost[minnode] + price[minnode][j];
}
}
}
}

int main(){
int a, b, d, p;
while(cin >> n >> m){
if(n == 0 && m == 0) break;
init();
for(int i = 0; i < m; i++){
cin >> a >> b >> d >> p;
if(length[a][b] > d) length[a][b] = length[b][a] = d;
if(price[a][b] > p) price[a][b] = price[b][a] = p;
}
cin >> s >> t;
Djikstra(s);
if(dis[t] == INF) printf("-1\n");
else printf("%d %d\n", dis[t], cost[t]);
}

}

是因为输入的时候虽然考虑了多次输入同一条路的情况，但没有考虑完全。
改了73行之后的部分，就通过了。

#include <iostream>

using namespace std;

const int N = 1000;
const int INF = 10000000;

int n, m, s, t;
int length[N][N];
int price[N][N];
int dis[N];
int cost[N];
int vis[N];

void init(){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            length[i][j] = INF;
            price[i][j] = INF;
        }
    }
}

void Djikstra(int s){
    int i, j;
    for(i = 1; i <= n; i++){
        dis[i] = length[s][i];
        cost[i] = price[s][i];
        vis[i] = 0;
    }
    dis[s] = 0;
    cost[s] = 0;
    vis[s] = 1;
    int mindis, mincost, minnode;
    for(i = 1; i <= n; i++){
        mindis = mincost = INF;
        minnode = 0;
        for(j = 1; j <= n; j++){
            if(!vis[j] && mindis == dis[j]){
                if(mincost > cost[j]){
                    minnode = j;
                    mincost = cost[j];
                }
            }
            if(!vis[j] && mindis > dis[j]){
                minnode = j;
                mindis = dis[j];
            }
        }
        if(mindis == INF) break;
        vis[minnode] = 1;
        for(j = 1; j <= n; j++){
            if(!vis[j] && dis[j] == dis[minnode] + length[minnode][j]){
                if(cost[j] > cost[minnode] + price[minnode][j]){
                    cost[j] = cost[minnode] + price[minnode][j];
                }
            }
            if(!vis[j] && dis[j] > dis[minnode] + length[minnode][j]){
                dis[j] = dis[minnode] + length[minnode][j];
                cost[j] = cost[minnode] + price[minnode][j];
            }
        }
    }
}

int main(){
    int a, b, d, p;
    while(cin >> n >> m){
        if(n == 0 && m == 0) break;
        init();
        for(int i = 0; i < m; i++){
            cin >> a >> b >> d >> p;
            if(length[a][b] > d){
                length[a][b] = length[b][a] = d;
                price[a][b] = price[b][a] = p;
            }
            else if(d == length[a][b] && p < price[a][b]){
                price[a][b] = price[b][a] = p;
            }
        }
        cin >> s >> t;
        Djikstra(s);
        if(dis[t] == INF) printf("-1\n");
        else printf("%d %d\n", dis[t], cost[t]);
    }

}