CSU 1808: 地铁（边最短路）

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL,int>P;
const int maxn=200000+100;
const LL INF=1e18;

struct Edge{
  
  int to,id,len,next;
}edge[maxn];
int head[maxn],tot;
bool vis[maxn];
LL dis[maxn];
int n,m;

LL Dijkstra(){
  
  priority_queue<P,vector<P>,greater<P> >que;
  for(int i=head[1];i!=-1;i=edge[i].next){
    
    dis[i]=edge[i].len;
    que.push(make_pair(dis[i],i));
  }
  while(!que.empty()){
    
    P p=que.top();
    que.pop();
    int edgeid=p.second;
      int u=edge[edgeid].to;
      if(u==n) return dis[edgeid];
      vis[edgeid]=true;
      for(int i=head[u];i!=-1;i=edge[i].next){
        
        Edge e=edge[i];
        if(!vis[i] && dis[i]>dis[edgeid]+e.len+abs(e.id-edge[edgeid].id)){
          
          dis[i]=dis[edgeid]+e.len+abs(e.id-edge[edgeid].id);
          que.push(make_pair(dis[i],i));
      }
    }
  }
}

int main(){
  
  while(scanf("%d%d",&n,&m)==2){
    
    tot=0;
    for(int i=1;i<=n;i++) head[i]=-1;
    for(int i=1;i<=m;i++){
      
      int u,v,id;
      LL len;
      scanf("%d%d%d%d",&u,&v,&id,&len);
      vis[tot]=false;
      dis[tot]=INF;
      edge[tot].to=v;
      edge[tot].id=id;
      edge[tot].len=len;
      edge[tot].next=head[u];
      head[u]=tot++;
      vis[tot]=false;
      dis[tot]=INF;
      edge[tot].to=u;
      edge[tot].id=id;
      edge[tot].len=len;
      edge[tot].next=head[v];
      head[v]=tot++;
    }
    printf("%lld\n",Dijkstra());
  }
}