初中组。。唉
题意有点误解，当前在x点走一步，gps产生代价条件是沿非x到n的最短路走。
直接倒着跑两遍$isim n$的两种最短路，然后枚举每条边走的时候是否可以在两种最短路上，不是就产生1个代价，然后以这个代价重新建图正着跑一遍最短路即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define dbg(x) cerr << #x << " = " << x <<endl 8 using namespace std; 9 typedef long long ll; 10 typedef double db; 11 typedef pair<int,int> pii; 12 typedef pair<ll,int> plli; 13 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 14 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 15 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;} 16 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;} 17 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;} 18 template<typename T>inline T read(T&x){ 19 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 20 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 21 } 22 const int N=1e5+7,M=5e5+7; 23 struct thxorz{int to,nxt,w1,w2;}G[M]; 24 struct stothx{int u,v,w1,w2;}e[M]; 25 int Head[N],tot; 26 int n,m; 27 inline void Addedge(int x,int y,int z1,int z2){ 28 G[++tot].to=y,G[tot].nxt=Head[x],Head[x]=tot,G[tot].w1=z1,G[tot].w2=z2; 29 } 30 ll dis1[N],dis2[N]; 31 priority_queue<plli,vector<plli>,greater<plli> > q; 32 #define y G[j].to 33 inline void dij1(int s){ 34 memset(dis1,0x3f,sizeof dis1),q.push(make_pair(dis1[s]=0,s)); 35 while(!q.empty()){ 36 ll d=q.top().first;int x=q.top().second;q.pop(); 37 if(dis1[x]^d)continue; 38 for(register int j=Head[x];j;j=G[j].nxt)if(d+G[j].w1<dis1[y])q.push(make_pair(dis1[y]=d+G[j].w1,y)); 39 } 40 } 41 inline void dij2(int s){ 42 memset(dis2,0x3f,sizeof dis2),q.push(make_pair(dis2[s]=0,s)); 43 while(!q.empty()){ 44 ll d=q.top().first;int x=q.top().second;q.pop(); 45 if(dis2[x]^d)continue; 46 for(register int j=Head[x];j;j=G[j].nxt)if(d+G[j].w2<dis2[y])q.push(make_pair(dis2[y]=d+G[j].w2,y)); 47 } 48 } 49 #undef y 50 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout); 51 read(n),read(m); 52 for(register int i=1;i<=m;++i) 53 read(e[i].u),read(e[i].v),read(e[i].w1),read(e[i].w2),Addedge(e[i].v,e[i].u,e[i].w1,e[i].w2); 54 dij1(n),dij2(n); 55 tot=0,memset(Head,0,sizeof Head); 56 for(register int i=1;i<=m;++i) 57 Addedge(e[i].u,e[i].v,(dis1[e[i].v]+e[i].w1!=dis1[e[i].u])+(dis2[e[i].v]+e[i].w2!=dis2[e[i].u]),0); 58 dij1(1); 59 return printf("%lld ",dis1[n]),0; 60 }
总结：对于题目跑图有奇怪的代价的，尝试重新建图，并且不妨通过跑额外最短路等手段来获取建图数据。