【AC】
#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=5e2+2; const int maxm=1e5+2; int n,m; struct edge{ int t; int to; int nxt; ll w; }e[2*maxm]; struct node{ int id; ll d; ll fa; node(int _id,ll _d,ll _fa):id(_id),d(_d),fa(_fa){} bool operator < (const node& a) const{ if(d!=a.d) return d>a.d; return fa>a.fa; } }; int head[maxn]; int tot; ll dis[maxn]; ll fa[maxn]; bool vis[maxn]; void init(){ memset(head,-1,sizeof(head)); tot=0; } void add(int t,int u,int v,ll w){ e[tot].t=t; e[tot].to=v; e[tot].w=w; e[tot].nxt=head[u]; head[u]=tot++; } ll dijkstra(int s){ memset(dis,inf,sizeof(dis)); memset(fa,inf,sizeof(fa)); memset(vis,false,sizeof(vis)); dis[s]=0,fa[s]=0; priority_queue<node> Q; Q.push(node(s,dis[s],fa[s])); while(!Q.empty()){ node q=Q.top(); Q.pop(); int u=q.id; if(vis[u]) continue; vis[u]=true; for(int i=head[u];i!=-1;i=e[i].nxt){ int t=e[i].t; int v=e[i].to; ll w=e[i].w; if(t==0){ if(dis[u]+w<=dis[v]){ dis[v]=dis[u]+w; fa[v]=0; Q.push(node(v,dis[v],fa[v])); } }else{ ll tmp=(fa[u]+w)*(fa[u]+w)+dis[u]-fa[u]*fa[u]; if(tmp<dis[v]){ dis[v]=tmp; fa[v]=fa[u]+w; Q.push(node(v,dis[v],fa[v])); }else if(tmp==dis[v]){ if(fa[u]+w<fa[v]){ fa[v]=fa[u]+w; Q.push(node(v,dis[v],fa[v])); } } } } } return dis[n]; } int main(){ while(~scanf("%d%d",&n,&m)){ init(); int t,u,v; ll w; for(int i=1;i<=m;i++){ scanf("%d%d%d%lld",&t,&u,&v,&w); add(t,u,v,w); add(t,v,u,w); } ll ans=dijkstra(1); printf("%lld ",ans); } return 0; }