题目传送门
代码：
#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());}
}