本文共 1791 字，大约阅读时间需要 5 分钟。
题目本质要求的还是最短路，但因为有第二维权值(汽水看成$+1$，汉堡看成$-1$)的限制，我们在最短路的基础上加上一维$f[i][j]$表示到达$i$节点，权值为$j$的最短路长度，然后像正常最短路那样转移，最后取终点所有状态的最小值即可。
#include #include #include #include #include #include #include #include #include #include #include using namespace std;struct lty{ int val,node,num; lty(int a,int b,int c){val=a,node=b,num=c;} };bool operator <(lty x,lty y){return x.val>y.val;}int f[10010][30];int head[10010];int val[200010];int v[10010];int to[200010];int next[200010];int n,m,k;int T;int tot;int a,b;int x,y,z;int vis[10010][30];priority_queue q;void add(int x,int y,int z){ next[++tot]=head[x]; head[x]=tot; to[tot]=y; val[tot]=z;}void init(){ memset(vis,0,sizeof(vis)); memset(head,0,sizeof(head)); tot=0;}void dijkstra(int S,int T){ for(int i=1;i<=n;i++) { for(int j=0;j<=2*k;j++) { f[i][j]=1<<30; } } f[S][k+v[S]]=0; q.push(lty(f[S][k+v[S]],S,k+v[S])); while(!q.empty()) { lty now=q.top(); q.pop(); if(vis[now.node][now.num]) { continue; } vis[now.node][now.num]=1; for(int i=head[now.node];i;i=next[i]) { if(now.num+v[to[i]]<0||now.num+v[to[i]]>2*k)continue; if(f[to[i]][now.num+v[to[i]]]>f[now.node][now.num]+val[i]) { f[to[i]][now.num+v[to[i]]]=f[now.node][now.num]+val[i]; q.push(lty(f[to[i]][now.num+v[to[i]]],to[i],now.num+v[to[i]])); } } } int ans=1<<30; for(int i=0;i<=2*k;i++) { ans=min(ans,f[T][i]); } printf("%d",ans==(1<<30)?-1:ans);}void solve(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) { scanf("%d",&v[i]); if(v[i]==2) { v[i]=-1; } } for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } scanf("%d%d",&a,&b); dijkstra(a,b);}int main(){ scanf("%d",&T); while(T--) { init(); solve(); }}
转载于:https://www.cnblogs.com/Khada-Jhin/p/10835688.html