浙大机试_最短路问题

题目描述

给你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)

输出描述:

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

示例1

输入

3 2
1 2 5 6
2 3 4 5
1 3
0 0

输出

9 11

最短路，去重，去重，去重！！！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
#define V 1005
#define E 200005
#define INT_MAX 2100000000

struct Eage
{
    int w,len,cost,next;
} eage[E];
int head[V],cnte;

void addEage(int v,int w,int l,int c)
{
    eage[cnte].w=w;
    eage[cnte].len=l;
    eage[cnte].cost=c;
    eage[cnte].next=head[v];
    head[v]=cnte++;
}

int n,m;


int dist[V],has[V],spen[V];
void dijkstra(int s)
{
    for(int i=1; i<=n; i++)
    {
        dist[i]=INT_MAX;
        has[i]=0;
    }
    dist[s]=0;
    has[s]=1;
    spen[s]=0;
    for(int i=head[s]; i!=0; i=eage[i].next)
    {
        int w=eage[i].w;
        if(dist[w]>eage[i].len)
        {
            dist[w]=eage[i].len;
            spen[w]=eage[i].cost;
        }
    }
    for(int i=1; i<n; i++)
    {
        int minx=INT_MAX,minloc;
        for(int j=1; j<=n; j++)
            if(dist[j]<minx&&has[j]==0)
            {
                minx=dist[j];
                minloc=j;
            }
        has[minloc]=1;
        for(int j=head[minloc]; j!=0; j=eage[j].next)
        {
            int w=eage[j].w;
            int l=eage[j].len;
            int c=eage[j].cost;
            if(dist[w]>=dist[minloc]+l)
            {
                if(dist[w]==dist[minloc]+l)
                    spen[w]=min(spen[w],spen[minloc]+c);
                else
                    spen[w]=spen[minloc]+c;
                dist[w]=dist[minloc]+l;
            }
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF&&(n&&m))
    {
        cnte=1;
        for(int i=1; i<=n; i++)
            head[i]=0;
        for(int i=0; i<m; i++)
        {
            int w,v,l,c;
            scanf("%d%d%d%d",&v,&w,&l,&c);
            addEage(v,w,l,c);
            addEage(w,v,l,c);
        }
        int s,t;
        scanf("%d%d",&s,&t);
        dijkstra(s);
        printf("%d %d
",dist[t],spen[t]);
    }
    return 0;
}