028：最短路径问题

Messj

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


Input
输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)


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


Sample Input
3 2  1 2 5 6  2 3 4 5  1 3  0 0


Sample Output
9 11

题目解析：注意两点
1、去掉重复的路径，选择较短的。读入重时时如果路径长度相同，则选择花费较小的。
2、不能用记录路径然后回溯的方法求最小花费，因为如果某两点之间有多条路径相等，则路径只能记录一种，不能根据此得出花费，应该先按照路径松弛，如果路径相等的话按照花费松弛！

Messj

点的数目远远超过200，Floyd算法的时间复杂度就超过了千万级别。因此只能使用dijkstra算法

#include<cstdio>
#include<vector>
#define N 1001

using namespace std; 

struct E
{
        int next;
        int c;
        int cost;
};
vector<E> edge[N];
bool mark[N];
int dis[N];
int cost[N];
int main()
{
        int n,m;
        int S,T;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
                if(n==0&&m==0)        break;
                for(int i=1;i<=n;i++)        edge[i].clear();
                while(m--)
                {
                        int a,b,c,cost;
                        scanf("%d%d%d%d",&a,&b,&c,&cost);
                        E tmp;
                        tmp.c=c;
                        tmp.cost=cost;
                        tmp.next=b;
                        edge[a].push_back(tmp);
                        tmp.next=a;
                        edge[b].push_back(tmp);
                }
                scanf("%d%d",&S,&T);
                for(int i=1;i<=n;i++)
                {
                        dis[i]=-1;
                        mark[i]=false;
                }
                dis[S]=0;
                cost[S]=0;
                mark[S]=true;        //点1加入集合 
                int newP=S;                //新加入集合的点为点1 
                for(int i=1;i<n;i++)
                {
                        for(int j=0;j<edge[newP].size();j++)
                        {
                                int t=edge[newP][j].next;
                                int c=edge[newP][j].c;
                                int co=edge[newP][j].cost;
                                if(mark[t]==true)        continue;
                                if(dis[t]==-1||dis[t]>(dis[newP]+c||dis[t]==dis[newP]+c&&cost[t]>cost[newP]+co))
                                {
                                        dis[t]=dis[newP]+c;
                                        cost[t]=cost[newP]+co;
                                }
                        }
                        int min=123123123;
                        for(int j=1;j<=n;j++)
                        {
                                if(mark[j])        continue;
                                if(dis[j]==-1)        continue;
                                if(dis[j]<min)
                                {
                                        min=dis[j];
                                        newP=j;
                                }
                        }
                        mark[newP]=true; 
                }
                printf("%d %d\n",dis[T],cost[T]);
        }
}