HDU3790 最短路径问题(dijkstra+思维)

#include <bits/stdc++.h>
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;
int n,m,num,s,t;
struct Node{
  int to,w,next,l;
  bool operator < (const Node &a) const{
    return a.l < l;
  }
}Edge[maxn],Now,Next;
int head[maxn];

void init(){
  memset(head,-1,sizeof(head));
  num = 0;
}

void add(int u,int v,int l,int w){
  Edge[num].to = v;
  Edge[num].w = w;
  Edge[num].l = l;
  Edge[num].next = head[u];
  head[u] = num++;
}

void dijkstra(int x){
  bool vis[maxn];
  int dist[maxn];
  int cost[maxn];
  memset(cost,0,sizeof(cost));
  memset(dist,inf,sizeof(dist));
  memset(vis,false,sizeof(vis));
  priority_queue<Node> q;
  Now.to = x;
  Now.w = 0;
  Now.next = 0;
  dist[x] = 0;
  q.push(Now);
  while(!q.empty()){
    Now = q.top();
    q.pop();
    int ans = Now.to;
    if(vis[ans])
      continue;
    vis[ans] = true;
    for(int i=head[ans];i!=-1;i=Edge[i].next){
      int u = Edge[i].to;
      if(!vis[u] && dist[u] > dist[ans] + Edge[i].l){
        dist[u] = dist[ans] + Edge[i].l;
        cost[u] = cost[ans] + Edge[i].w;
      }
      else if(!vis[u] && dist[u] == dist[ans] + Edge[i].l && cost[u] > cost[ans] + Edge[i].w){
        cost[u] = cost[ans] + Edge[i].w;
      }
      Next.to = u;
      Next.w = cost[u];
      Next.l = dist[u];
      q.push(Next);
    }
  }
  printf("%d %d\n",dist[t], cost[t]);
}

int main()
{
  while(~scanf("%d%d",&n,&m)){
    if(n == 0 && m == 0)break;
    init();
    for(int i=0;i<m;i++){
      int u,v,w,l;
      scanf("%d%d%d%d",&u,&v,&l,&w);
      add(u, v, l, w);
      add(v, u, l, w);
    }
    scanf("%d%d",&s,&t);
    dijkstra(s);
  }
  return 0;
}