[SPFA]hdoj 3790：最短路径问题

大致题意：
    给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

 

大致思路：
    最短路稍稍变形，加入一个val限制即可

 

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=3050;
const int mMax=1000050;
const int inf=1<<28;
struct{
    int v, next;
    int  w,val;
}edge[mMax];
int n, k, edgeHead[nMax],rehead[nMax],rk;
int dis[nMax],issea[nMax];
int stack[nMax],m,val[nMax];
bool vis[nMax];

void addedge(int a,int b,int w,int val){
    edge[k].w = w;
    edge[k].v=b;
    edge[k].val=val;
    edge[k].next=edgeHead[a];
    edgeHead[a]=k;k++;
}

int spfa(int s){
    int i, top = 0;
    memset(vis,0,sizeof(vis));
    for(i=1;i<=n;i++){
        dis[i]=inf;
        val[i]=inf;
    }
    dis[s]=0;
    val[s]=0;
    stack[++top]=s;
    vis[s]=true;
    while(top){
        int u=stack[top--];
        vis[u]=false; /////////////////
        for(i=edgeHead[u];i!=0;i=edge[i].next){
            int v=edge[i].v;
            if(dis[v]>dis[u]+edge[i].w){
                dis[v]=dis[u]+edge[i].w;
                val[v]=val[u]+edge[i].val;
                if(!vis[v]){
                    vis[v]=true;
                    stack[++top] = v;
                }
            }
            if(dis[v]==dis[u]+edge[i].w&&val[v]>val[u]+edge[i].val){
                dis[v]=dis[u]+edge[i].w;
                val[v]=val[u]+edge[i].val;
                if(!vis[v]){
                    vis[v]=true;
                    stack[++top] = v;
                }
            }
        }
    }
    int sum=0;
    for(i=1;i<=n;i++){
        sum+=dis[i];
    }
    return sum;
}

int main(){
    int i,j,s,t,a,b,c,d;
    while(scanf("%d%d",&n,&m)&&(n||m)){
        k=1;
        memset(edgeHead,0,sizeof(edgeHead));
        while(m--){
            scanf("%d%d%d%d",&a,&b,&c,&d);
            addedge(a,b,c,d);
            addedge(b,a,c,d);
        }
        scanf("%d%d",&s,&t);
        spfa(s);
        cout<<dis[t]<<" "<<val[t]<<endl;
    }
    return 0;
}