最短路径问题

题目描述：: 给你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)

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

样例输入：

样例输出：

9 11

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;

struct e{
    int next,c,cost;
};
vector<e> edge[1001];
bool mark[1001];
int dis[1001];
int costt[1001];

int main (){
    int n,m;
    while (cin>>n>>m && n!=0 && m!=0){
        int a,b,c,cost;
        e temp;
        //初始化 
        for (int i=1;i<=n;i++){
            edge[i].clear();
            dis[i]=-1;
            mark[i]=false;
        }
        
        
        
        while(m--){
            cin>>a>>b>>c>>cost;
            temp.cost=cost;
            temp.c=c;
            temp.next=a;
            edge[b].push_back(temp);
            temp.next=b;
            edge[a].push_back(temp);
        }
        
        int ss,dd;
        cin>>ss>>dd;
        costt[ss]=0;
        dis[ss]=0;
        mark[ss]=true;
        int newp=ss;
        for (int i=1;i<n;i++){
            for (int j=0;j<edge[newp].size();j++){
                int nex=edge[newp][j].next;
                int c = edge[newp][j].c;
                int co =edge[newp][j].cost;
                if (mark[nex] == true)
                continue;
                if (dis[nex]==-1 || dis[nex]>dis[newp]+c ||
                    (dis[nex] ==dis[newp]+c && costt[nex]>costt[newp]+co))//floyd也有若不可达或者比之小，不知道为啥要有不可达，先记住 
                {
                    dis[nex] = dis[newp]+c;
                    costt[nex] = costt[newp]+co;
                }
                
            }
            int min=100000000;
            for (int j=1;j<=n;j++){
                if (mark[j] == true)
                continue;
                if (dis[j] == -1)//因为我们的无穷大不是无穷，而是-1，之后的比大小有影响 
                continue;       //所以要加上这个条件
                if(dis[j]<min){
                    min = dis[j];
                    newp=j;
                }  
            }
            mark[newp]=true;
            
            
        }
    cout<<dis[dd]<<" "<<costt[dd]<<endl;
    }

    return 0;

}

这与普通dijstra的区别是判断短距离，标红了

比较大小时，将距离相同但花费更短也作为更新的条件之一