BZOJ 2763: [JLOI2011]飞行路线最短路

2019-11-06 06:57:02

字体：大中小

来源：转载

供稿：网友

题目链接:

http://www.lydsy.com/JudgeOnline/PRoblem.php?id=2763

题意:

题解:

最短路，在转移dis的时候多开一维k就好了 dis[i][j]->dis[t][j]+e[i][t] dis[i][j]->dis[t][j+1] if j

代码:

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define MS(a) memset(a,0,sizeof(a))#define MP make_pair#define PB push_backconst int INF = 0x3f3f3f3f;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;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;}//////////////////////////////////////////////////////////////////////////const int maxn = 1e5+10;struct node{ int x,y;};vector<node> E[maxn];ll dis[maxn][15];int inq[maxn][15];int main(){ int n,m,k,s,t; scanf("%d%d%d%d%d",&n,&m,&k,&s,&t); for(int i=0; i<m; i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); E[u].push_back(node{v,w}); E[v].push_back(node{u,w}); } for(int i=0; i<=n; i++) for(int j=0; j<=k; j++) dis[i][j] = INF; memset(inq,0,sizeof(inq)); queue<node> q; q.push((node){s,0}); inq[s][0] = 1, dis[s][0] = 0; while(!q.empty()){ node now = q.front(); q.pop(); inq[now.x][now.y] = 0; for(int i=0; i<(int)E[now.x].size(); i++){ int v = E[now.x][i].x, w = E[now.x][i].y; if(dis[v][now.y] > dis[now.x][now.y]+w){ // 不用票 dis[v][now.y] = dis[now.x][now.y]+w; if(!inq[v][now.y]){ inq[v][now.y] = 1; q.push((node){v,now.y}); } } if(dis[v][now.y+1]>dis[now.x][now.y] && now.y<k){ // 用票 dis[v][now.y+1] = dis[now.x][now.y]; if(!inq[v][now.y+1]){ inq[v][now.y+1] = 1; q.push((node){v,now.y+1}); } } } } ll ans = INF; for(int i=0; i<=k; i++) if(dis[t][i] < ans) ans = dis[t][i]; cout << ans << endl; return 0;}

上一篇：PAT--1125. Chain the Ropes

下一篇：HTML入门详解