洛谷题解

#include<bits/stdc++.h> #define N 1000010 #define int long long using namespace std; inline void read(int& x) { x=0;int y=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')y=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x10+ch-'0';ch=getchar();} x=xy; } int n,m; struct Node{ int to,nxt,w,col; }e[N<<1]; int cnt,head[N]; inline void add(int u,int v,int col,int w) { e[++cnt].col=col;e[cnt].nxt=head[u],e[cnt].to=v,e[cnt].w=w; head[u]=cnt; } int vis[N],num[N],sum[N],rt[N],tot,d[N]; struct node{ int dis,id; bool operator<(const node& x)const{return dis>x.dis;} node(){} node(int d_,int id_){dis=d_,id=id_;} }; priority_queue<node> q; inline void dij() { memset(d,0x3f,sizeof(d)); d[1]=0; q.push(node(d[1],1)); while(!q.empty()) { int x=q.top().id;q.pop(); if(vis[x])continue;vis[x]=1; for(int i=head[x];i;i=e[i].nxt) { int y=e[i].to,w=e[i].w; if(d[y]>d[x]+w) { d[y]=d[x]+w; q.push(node(d[y],y)); } } } } signed main(){ // freopen("robot.in","r",stdin); // freopen("robot.out","w",stdout); read(n),read(m); for(int i=1;i<=m;i++) { int x,y,z,zz; read(x),read(y),read(z),read(zz); add(x,y,z,zz),add(y,x,z,zz); } tot=n; //-------------------重点分割线--------------------------- //这一段是关于建虚点的 for(int x=1;x<=n;x++) { for(int i=head[x];i;i=e[i].nxt) { if(!e[i].col)continue; sum[e[i].col]+=e[i].w; num[e[i].col]++; //sum表示同色点的权值和，num表示该颜色点有几个 } for(int i=head[x];i;i=e[i].nxt) { int y=e[i].to; if(!e[i].col)continue; if(num[e[i].col]==1)e[i].w=0;//仅一个，花费为0 else { if(!rt[e[i].col]) //2类边，蓝->黑 //rt记录了每一种颜色的虚点编号 { rt[e[i].col]=++tot; add(x,tot,0,0); } add(rt[e[i].col],e[i].to,0,sum[e[i].col]-e[i].w); //3类边，黑->红，权值为sum[e[i].col]-e[i].w add(e[i].to,rt[e[i].col],0,0); //4类边，红->黑，权值为0 } } for(int i=head[x];i;i=e[i].nxt) { rt[e[i].col]=sum[e[i].col]=num[e[i].col]=0; } //别忘了清空数组 //由于一个点的度数不会太大，所以直接改会比memset快一点 } //-------------------重点分割线--------------------------- dij(); if(d[n]==0x3f3f3f3f3f3f3f3f)printf("-1\n"); else printf("%lld\n",d[n]); return 0; }