题目链接

题目描述

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

则输出花费最少的。

最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。(1<n<=1000, 0<m<100000, s != t)

Spfa模板题：

#include <set>

#include <map>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int, int> pa;

typedef long long  LL;

const int inf=1e9;//INT_MAX;

//SPFA

const int maxn=1000+5;

struct node

{

    int ed;

    int len;

    int cast;

};

struct node2

{

    int i;

    int sum;

};

node2 dis[maxn];

int inque[maxn];

int n,m;

vector<node>E[maxn];

queue<int>que;

void Spfa(int st,int ed)

{

    for(int i=1;i<=n;i++)

        dis[i].i=inf,dis[i].sum=inf,inque[i]=false;

    while(!que.empty())

        que.pop();

    que.push(st);

    inque[st]=true;

    dis[st].i=0;

    dis[st].sum=0;

    while(!que.empty())

    {

        int pos=que.front();

        que.pop();

        inque[pos]=false;

        int l=int(E[pos].size());

        for(int i=0;i<l;i++)

        {

            int en=E[pos][i].ed;

            int le=E[pos][i].len;

            int ca=E[pos][i].cast;

            int x=dis[pos].i+le;

            //int c=dis[pos].cast+ca;

            if(dis[en].i>=x)//关键点，要考虑优先级

            {

                if(dis[en].i>x)

                {

                    dis[en].i=x;

                    dis[en].sum=dis[pos].sum+ca;

                }

                else if(dis[en].sum>dis[pos].sum+ca)

                {

                    dis[en].i=x;

                    dis[en].sum=dis[pos].sum+ca;

                }

                if(!inque[en])

                    que.push(en);

            }

        }

    }

}

int main ()

{

    while(~scanf("%d%d",&n,&m))

    {

        if (n==0&&m==0)

            break;

        for(int i=0;i<=n;i++)

            E[i].clear();

        int st,ed,len,cast;

        for(int i=0;i<m;i++)

        {

            scanf("%d%d%d%d",&st,&ed,&len,&cast);

            node x1={ed,len,cast};

            E[st].push_back(x1);

            node x2={st,len,cast};

            E[ed].push_back(x2);

        }

        int s,d;

        scanf("%d%d",&s,&d);

        Spfa(s, d);

        printf("%d %d\n",dis[d].i,dis[d].sum);

    }

    return 0;

}