【链接】 我是链接,点我呀:)
【题意】

在这里输入题意

【题解】

定义dis[i][j]表示到达i这个点。
用掉了j次去除边的机会的最短路。
dis[1][0]= 0;
在写松弛条件的时候。
如果用了去除边的机会。
就把机会+1再更新最短路就好。
用spfa会超时。
写个dijkstra+优先队列优化就ok
在dis[n][0..k]中找最小值就好。

【代码】

#include <bits/stdc++.h> #define LL long long #define ms(a,b) memset(a,b,sizeof a) #define rep1(i,a,b) for (int i = a;i <= b;i++) #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) const LL mod=1000000007; LL powmod(LL a,LL b) {LL res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} LL gcd(LL a,LL b) { return b?gcd(b,a%b):a;} // head using namespace std; const int N = 1e5; const int K = 10; const int M = 2e5; struct abc { int en,w,nex; }bian[M+10]; int n,m,k,fir[N+10],totm; LL dis[N+10][K+5]; multiset< pair<LL,pair<int,int> > > myset; multiset< pair<LL,pair<int,int> > >::iterator it; int main(){ while (n>0){ n/=2; n++; n--; n/=2; } ios::sync_with_stdio(0),cin.tie(0); int T; cin >> T; while (T--){ memset(fir,255,sizeof fir); totm = 0; cin >> n >> m >> k; rep1(i,1,m){ int x,y,z; cin >> x >> y >> z; totm++; bian[totm].nex = fir[x]; fir[x] = totm; bian[totm].en = y; bian[totm].w = z; } memset(dis,255,sizeof dis); dis[1][0] = 0; myset.insert(make_pair(0,make_pair(1,0))); while (!myset.empty()){ pair<LL,pair<int,int> > temp = (*myset.begin()); myset.erase(myset.begin()); int x = temp.second.first,times = temp.second.second; for (int i = fir[x];i!=-1;i = bian[i].nex) { int y = bian[i].en;LL w = bian[i].w; if (dis[y][times]==-1 || dis[y][times]>dis[x][times]+w){ if (dis[y][times]!=-1){ it = myset.find(make_pair(dis[y][times],make_pair(y,times))); myset.erase(it); } dis[y][times] = dis[x][times]+w; myset.insert(make_pair(dis[y][times],make_pair(y,times))); } if (times+1<=k && ( dis[y][times+1]==-1 || dis[y][times+1]>dis[x][times])) { if (dis[y][times+1]!=-1) { it = myset.find(make_pair(dis[y][times+1],make_pair(y,times+1))); myset.erase(it); } dis[y][times+1] = dis[x][times]; myset.insert(make_pair(dis[y][times+1],make_pair(y,times+1))); } } } LL mi = dis[n][0]; for (int i = 1;i <= k;i++) if (dis[n][i]!=-1){ mi = min(mi,dis[n][i]); } cout<<mi<<endl; } return 0; }

转载于:https://www.cnblogs.com/AWCXV/p/9580802.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/99852152

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。