hdu 3790 最短路问题 (spfa练手)

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 Input3 21 2 5 62 3 4 51 3
0 0 Sample Output9 11 

#include <cstdio>#include <map>#include <iostream>#include<cstring>#include<bits/stdc++.h>#define ll long long int#define M 6using namespace std;inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}]={,,,,,,,,,,,,};][]={, ,, ,-, ,,-};][]={, ,, ,-, ,,-, -,- ,-, ,,- ,,};const int inf=0x3f3f3f3f;;struct node{    int next;    int to;    int d,p;};node edge[];];int cnt;void add(int u,int v,int d,int p){    edge[++cnt].next=head[u];    edge[cnt].to=v;    edge[cnt].d=d;    edge[cnt].p=p;    head[u]=cnt;}int n,m;int s,e;];],cost[];void spfa(int x){    ;i<=n;i++){        dis[i]=inf;        cost[i]=inf;    }    dis[x]=cost[x]=;    memset(vis,,sizeof(vis));    queue<int > q;    q.push(x);    vis[x]=;    while(!q.empty()){        int u=q.front();        q.pop();        vis[u]=;        ;i=edge[i].next){            int to=edge[i].to; int d=edge[i].d; int p=edge[i].p;            if(dis[to]>dis[u]+d||((dis[to]==dis[u]+d)&&(cost[to]>cost[u]+p))){                cost[to]=cost[u]+p;                dis[to]=dis[u]+d;                if(!vis[to]){                    q.push(to);                    vis[to]=;                }            }        }    }}int main(){    //ios::sync_with_stdio(false);    while(scanf("%d%d",&n,&m)!=EOF){        if(!n&&!m) break;        memset(head,,sizeof(head));        cnt=;        ;i<=m;i++){            int a,b,d,p;            scanf("%d%d%d%d",&a,&b,&d,&p);            add(a,b,d,p);            add(b,a,d,p);        }        scanf("%d%d",&s,&e);        spfa(s);        printf("%d %d\n",dis[e],cost[e]);    }}