【题目描述】：

给你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时输入结束。

【输出描述】：

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

【样例输入】：

3 21 2 5 62 3 4 51 30 0

【样例输出】：

9 11

【时间限制、数据范围及描述】：

时间：1s 空间：128M

对于 30%的数据：1<n<=100

对于100%的数据：1<n<=1000; 0<m<100000; s != t; 1<=d,p<=1000

数据组数<=5，注意卡常;

 

题解：spfa，哇为什么就是过不了样例呢，找不出错误，难受.jpg

错解：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            typedef long long ll;using namespace std;const int oo=21474836;int n,m,k,cnt,x,y,z,dis[100005],vis[100005];struct node{ int to; int val; int next; int cos; }e[100005];int head[100004];int coo[100004],hh;void add(int a,int b,int c,int d){ cnt++; e[cnt].to=b; e[cnt].val=c; e[cnt].cos=d; e[cnt].next=head[a]; head[a]=cnt;}int main(){ freopen("216.in","r",stdin); freopen("216.out","w",stdout); while(1){ scanf("%d %d",&n,&m); queue
            
             q; cnt=0; if(n==0 && m==0) break; for(int i=1;i<=m;i++){ scanf("%d %d %d %d",&hh,&x,&y,&z); add(hh,x,y,z); add(x,hh,y,z); } memset(head,0,sizeof(head)); memset(e,0,sizeof(e)); memset(dis,0x3f,sizeof(dis)); memset(coo,0x3f,sizeof(coo)); memset(vis,0,sizeof(vis)); int s,t; scanf("%d %d",&s,&t); q.push(s); dis[s]=0; coo[s]=0; vis[s]=1; while(!q.empty()){ x=q.front(); q.pop(); vis[x]=0; for(int i=head[x];i!=0;i=e[i].next){ int too=e[i].to; if(dis[too]>dis[x]+e[i].val){ dis[too]=dis[x]+e[i].val; coo[too]=coo[x]+e[i].cos; if(vis[too]==0) { vis[too]=1; q.push(too); } } if(dis[too]==dis[x]+e[i].val && coo[x]+e[i].cos
            
           
          
         
        
       
      
     

 感谢srj大佬给予修改找bug！！！orzTQL

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           typedef long long ll;using namespace std;const int oo=21474836;int n,m,k,cnt,x,y,z,dis[1000005];//,vis[100005];struct node{ int to; int val; int next; int cos; }e[1000005];int head[1000005];int coo[1000005],hh;struct Node{ int pos,dis,cos; bool operator < ( const Node &a )const{ return a.dis==dis?a.cos
           
            
             q;void add(int a,int b,int c,int d){ cnt++; e[cnt].to=b; e[cnt].val=c; e[cnt].cos=d; e[cnt].next=head[a]; head[a]=cnt;}int main(){ freopen("216.in","r",stdin); freopen("216.out","w",stdout); while(1){ scanf("%d%d",&n,&m); cnt=0; if(n==0 && m==0) break; memset(head,0,sizeof(head)); memset(e,0,sizeof(e)); memset(dis,0x3f,sizeof(dis)); memset(coo,0x3f,sizeof(coo)); for(int i=1;i<=m;i++){ scanf("%d%d%d%d",&x,&hh,&y,&z); add(hh,x,y,z); add(x,hh,y,z); } int s,t; scanf("%d%d",&s,&t); q.push((Node){s,0,0}); dis[s]=0; coo[s]=0; while(!q.empty()){ Node tmp=q.top(); q.pop(); int x=tmp.pos; for(int i=head[x];i!=0;i=e[i].next){ int too=e[i].to; if(dis[too]>dis[x]+e[i].val){ dis[too]=dis[x]+e[i].val; coo[too]=coo[x]+e[i].cos; q.push((Node){too,dis[too],coo[too]}); } else if(dis[too]==dis[x]+e[i].val && coo[x]+e[i].cos