最短路径问题

一看到题就想到Dijkstra了。。但是突然看到两个权值懵逼了，看到讨论里面的大佬的代码才醒悟。
题目输入比较坑的一点是，前面输入的边的距离和花费，到后面可能会变，比如前面输入了 1 2 8 6，后面又输入 2 1 2 9这种。
所以在读入数据的时候（makeG函数），要判断一下。
Dijkstra没啥好说的，就是在更新的时候不同于传统的算法，首先是判断距离是不是更小，之后如果距离是相等的而花费更小，也要更新。（这就是一开始懵的地方了。。）
因为不要求输出源到汇的完整路径，所以不用path了，只保存dist和cost即可。

#include<stdio.h>
#include<limits.h>
#define NMAX 1001
int n,m;
int disG[NMAX][NMAX]; // 距离图
int costG[NMAX][NMAX]; // 花费图
int dis[NMAX]; // 源点到各点的距离
int cost[NMAX]; // 源点到各点的花费
int visit[NMAX]; // 当前结点是否遍历过

void init()
{
    for(int i = 1;i<=n;i++)
    {
        for (int j = 1; j <= n; j++)
        {
            disG[i][j] = i == j ? 0 : INT_MAX;
            costG[i][j] = i == j ? 0 : INT_MAX;
        }
        dis[i] = INT_MAX;
        cost[i] = INT_MAX;
        visit[i] = 0;
    }
    return;
}
void makeG()
{
    int x,y,dis,cost;
    for(int i = 0;i<m;i++)
    {
        scanf("%d %d %d %d",&x,&y,&dis,&cost);
        if(dis < disG[x][y]) // 如果当前输入的距离比原本更小则更新
        {
            disG[x][y] = dis;
            disG[y][x] = dis;
            costG[x][y] = cost;
            costG[y][x] = cost;
        }
        else if(dis == disG[x][y] && cost < costG[x][y]) // 如果距离相等而花费更小则更新
        {
            costG[x][y] = cost;
            costG[y][x] = cost;
        }
    }
}
int findminv() // 找出当前未遍历过的点且距离最短
{
    int min = INT_MAX;
    int minv = -1;
    for(int i = 1;i<=n;i++)
    {
        if(!visit[i] && dis[i] < min)
        {
            min = dis[i];
            minv = i;
        }
    }
    if(min < INT_MAX)
        return minv;
    else
        return -1;
}
void Dijkstra(int s)
{
    int minv;
    visit[s] = 1;
    for(int i = 1;i<=n;i++) // 把图的距离和花费数据更新到dis和cost中以便findminv
    {
        if(disG[s][i]!=INT_MAX)
        {
            dis[i] = disG[s][i];
            cost[i] = costG[s][i];
        }
    }
    while(1)
    {
        minv = findminv();
        if(minv == -1) // 全部遍历完
            break;
        else
        {
            visit[minv] = 1;
            for(int i = 1;i<=n;i++)
            {
                if(!visit[i] && disG[minv][i] < INT_MAX)
                {
                    if(dis[minv] + disG[minv][i] < dis[i]) // 距离更短
                    {
                        dis[i] = dis[minv] + disG[minv][i];
                        cost[i] = cost[minv] + costG[minv][i];
                    }
                    else if(dis[minv] + disG[minv][i] == dis[i] && cost[minv] + costG[minv][i] < cost[i])// 距离相等且花费更小
                        cost[i] = cost[minv] + costG[minv][i];
                }
            }
        }
    }

}
int main()
{
    int s,t;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        if(n == 0 && m == 0)
            break;
        init();
        makeG();
        scanf("%d %d", &s, &t);
        Dijkstra(s);
    }
    printf("%d %d\n",dis[t],cost[t]);
    return 0;
}