题意：
n点m mm边的图，每条边有边权和颜色，颜色有红蓝白三种，问从s ss到t tt恰好走k 1 k1k1条红边和k 2 k2k2条蓝边的最短距离。
思路：
dp[i][j][k]表示从s出发到达点i并且经过了j条红边，k条蓝边的最短距离。
转移就是普通的dijkstra转移，但是这样内存超限。
题目中有一个条件是k 1 ∗ k 2 < = 800如果我们始终把k值大的看做是红边，小的看做是蓝边，这样只需要开455 ∗ 801 ∗ 101的d p数组。
有一个剪枝就是，如果当前经过的红边> k 1或是蓝边> k 2，都一定不符合题意了，直接跳过即可，
参考博客
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=4e5+7,maxm=1e6+7,mod=1e9+7; int n,m,k1,k2,flag=0,s,t; struct node{ int e,ne,w,c; }edge[1100*2]; int h[1100],idx; ll dp[451][801][101]; struct node1{ ll d,id,t1,t2; bool operator<(const node1 &a)const{ return d>a.d; } }; priority_queue<node1>q; void add(ll u,ll v,ll w,ll c){ edge[idx]={v,h[u],w,c};h[u]=idx++; } void bfs(){ memset(dp,-1,sizeof dp); dp[s][0][0]=0; q.push({0,s,0,0}); while(!q.empty()){ node1 t=q.top();q.pop(); ll d=t.d,id=t.id,t1=t.t1,t2=t.t2; if(t1>k1||t2>k2) continue; for(int i=h[id];~i;i=edge[i].ne){ int j=edge[i].e,w=edge[i].w,c=edge[i].c; int now1=0,now2=0; if(c==1) now1=1; if(c==2) now2=1; if(dp[j][t1+now1][t2+now2]==-1||dp[j][t1+now1][t2+now2]>dp[id][t1][t2]+w){ dp[j][t1+now1][t2+now2]=dp[id][t1][t2]+w; q.push({dp[j][t1+now1][t2+now2],j,t1+now1,t2+now2}); } } } } int main() { memset(h,-1,sizeof h); n=read,m=read,k1=read,k2=read; if(k1<k2) swap(k1,k2),flag=1; for(int i=1;i<=m;i++){ ll u=read,v=read,w=read,c=read; if(flag){ if(c==1) c=2; else if(c==2) c=1; } add(u,v,w,c); add(v,u,w,c); } s=read,t=read; bfs(); printf("%lld\n",dp[t][k1][k2]); return 0; }
![[North Central NA Contest 2018] Rational Ratio | 规律 细节模拟](https://ucc.alicdn.com/pic/developer-ecology/55653cdbee054b3e99ef83f54def4175.png?x-oss-process=image/resize,h_160,m_lfit)