【牛客 - 370B】Rinne Loves Graph（分层图最短路 或 最短路dp）

网友投稿 226 2022-09-26

【牛客 - 370B】Rinne Loves Graph（分层图最短路 或 最短路dp）

题干：

Island 发生了一场暴乱！现在 Rinne 要和 Setsuna 立马到地上世界去。

众所周知：Island 是有一些奇怪的城镇和道路构成的（题目需要，游戏党勿喷），有些城镇之间用双向道路连接起来了，且每条道路有它自己的距离。但是有一些城镇已经被派兵戒严，虽然主角可以逆天改命强闯，但是为了体验该游戏的平衡性，他们只能穿过不超过 K 次被戒严的城镇。

定义“穿过”：从一个戒严的点出发到达任意一个点，都会使得次数加1

现在他们想从 1 号城镇最快的走到 n 号城镇（即出口），现在他们想让你告诉他们最短需要走多少路。

输入描述:

第一行三个整数 n,m,k，分别表示城镇数量，边数量和最多能闯过被戒严的城市的次数。接下来 n 行，每行一个整数 1 或 0，如果为 1 则表示该城市已被戒严，0 则表示相反。接下来 m 行，每行三个数 u,v,w，表示在 u 城镇和 v 城镇之间有一条长度为 w 的双向道路。

输出描述:

输出一行一个数字，表示从 1 到 n 的最短路径，如果到达不了的话，请输出 -1。

示例1

输入

复制

4 5 110101 2 102 3 103 1 151 4 603 4 30

输出

复制

60

备注:

2≤n≤800,1≤m≤4000,1≤k≤10,1≤w≤1062≤n≤800,1≤m≤4000,1≤k≤10,1≤w≤106

保证没有多条道路连接同一对城市，也没有一条道路连向自己。

解题报告：

这题可以dp，dp[i][j]表示从1到 i ，穿过j次戒烟戒严城镇，的最短路。（最近这种题见了三道了。）。也可以k - 分层图。（下面有好几个分层图代码，建图方式和做法有所不同）。也可以直接类似bfs的Dijkstra。。

AC代码1：（分层图）

#include#include#include#include#include#include#include#include#include#include#define ll long long#define pb push_back#define pm make_pairusing namespace std;const int MAX = 800 + 5;const int INF = 0x3f3f3f3f;int tot;int n,m,k;int a[MAX];int dis[MAX*15],head[MAX*15];bool vis[MAX*15];struct Edge { int to,ne; int w;} e[8005*15];struct Point { int id; int c; Point() {} Point(int id,int c):id(id),c(c) {} bool operator <(const Point & b) const { return c>b.c; }};void add(int u,int v,int w) { e[++tot].to = v; e[tot].w = w; e[tot].ne = head[u]; head[u] = tot;}void Dijkstra() { memset(dis,INF,sizeof dis); dis[1] = 0; priority_queue pq; pq.push(Point(1,0)); while(pq.size()) { Point cur = pq.top(); pq.pop();// if(vis[cur.id]) continue;这两句加不加都可以AC// vis[cur.id] = 1; for(int i = head[cur.id]; i!=-1; i = e[i].ne) { if(dis[e[i].to]>e[i].w+cur.c) { dis[e[i].to]=e[i].w+cur.c; pq.push(Point(e[i].to,dis[e[i].to])); } } }} int main(){ memset(head,-1,sizeof head); scanf("%d%d%d",&n,&m,&k); for (int i=1; i<=n; i++) scanf("%d",&a[i]); for (int i=1; i<=m; i++) { int x,y,w; scanf("%d%d%d",&x,&y,&w); if(!a[x]) { for(int j = 0; j<=k; j++) add(x+n*j,y+n*j,w); } if(!a[y]) { for(int j = 0; j<=k; j++) add(y+n*j,x+n*j,w); } if(a[x]) { for(int j = 0; j

一个大佬的分层图：

#include#include#include#includeusing namespace std;const int N=2e5+10;int a[N],he[N*10],t[N*20],ne[N*20],d[N*400],vis[N*10],tot=0;long long dis[N],cc[N*20];void link(int x,int y,long long z){ tot++; ne[tot]=he[x]; he[x]=tot; t[tot]=y; cc[tot]=z;}int main(){ int n,m,k; scanf("%d%d%d",&n,&m,&k); for (int i=1;i<=n;i++) scanf("%d",&a[i]); if (a[1]) k--; if (a[n]) k++; for (int i=1;i<=m;i++) { int x,y; long long z; scanf("%d%d%lld",&x,&y,&z); for (int j=0;j<=k;j++) { if (!a[x]) link(y+n*j,x+n*j,z); if (!a[y]) link(x+n*j,y+n*j,z); } for (int j=0;j

分层图标程：

#include #include #include #include #include #include #include #include #include #include #define LL long long const int MAXN = 800 + 5;const int MAXM = 4000 + 5;const int MAXK = 10 + 5; int N,M,K;using std::queue; struct Node{ struct Edge *firstEdge; LL dist; bool inQueue,die;}node[MAXN * MAXN + 2]; struct Edge{ Node *s,*t; LL w; Edge *next;}pool[MAXM * MAXK * 2],*frog = pool; Edge *New(Node *s,Node *t,LL w){ Edge *ret = ++frog; ret->s = s;ret->t = t; ret->w = w;ret->next = s->firstEdge; return ret;} inline void add(int u,int v,LL w){ node[u].firstEdge = New(&node[u],&node[v],w); //node[v].firstEdge = New(&node[v],&node[u],w);} LL SPFA(int s,int t,int n){ for(int i = 1;i <= n;i++){ node[i].dist = LLONG_MAX; node[i].inQueue = false; } queue q; q.push(&node[s]); node[s].inQueue = true; node[s].dist = 0; while(!q.empty()){ Node *v = q.front(); q.pop(); v->inQueue = false; for(Edge *e = v->firstEdge;e;e = e->next){ if(e->t->dist > v->dist + e->w){ e->t->dist = v->dist + e->w; if(!e->t->inQueue){ e->t->inQueue = true; q.push(e->t); } } } } return node[t].dist;} int main(){ scanf("%d%d%d",&N,&M,&K); for(int x,i = 1;i <= N;i++) scanf("%d",&node[i].die); int s = 0,t = N + N * K + 1; for(int u,v,i = 1;i <= M;i++){ LL w; scanf("%d%d%lld",&u,&v,&w); if(!node[u].die) for(int i = 0;i <= K;i++) add(u + N * i,v + N * i,w); if(!node[v].die) for(int i = 0;i <= K;i++) add(v + N * i,u + N * i,w); if(node[u].die) for(int i = 0;i < K;i++) add(u + N * i,v + N * (i + 1),w); if(node[v].die) for(int i = 0;i < K;i++) add(v + N * i,u + N * (i + 1),w); } add(s,1,0); for(int i = 0;i <= K;i++) add(N + (N * i),t,0); LL ans = SPFA(s,t,N*(1 + K) + 2); printf("%lld\n",(ans == LLONG_MAX) ? -1 : ans); //getchar();getchar(); return 0;}

AC代码3：（最短路dp）

#include#include#include#include#include#include#include#include#include#include#define ll long long#define pb push_back#define pm make_pairusing namespace std;const int MAX = 800 + 5;const int INF = 0x3f3f3f3f;int tot;int n,m,k;int a[MAX];int dis[MAX][15],head[MAX];//dis[i][j]表示从1到 i ，穿过j次戒烟戒严城镇，的最短路。struct Edge { int to,ne; int w;} e[4005*2];struct Point { int id; int c,jy; Point() {} Point(int id,int c,int jy):id(id),c(c),jy(jy) {} bool operator <(const Point & b) const { return c>b.c; }};void add(int u,int v,int w) { e[++tot].to = v; e[tot].w = w; e[tot].ne = head[u]; head[u] = tot;}void Dijkstra() { memset(dis,INF,sizeof dis); dis[1][0] = 0; priority_queue pq; pq.push(Point(1,0,0)); while(pq.size()) { Point cur = pq.top(); pq.pop(); for(int i = head[cur.id]; i!=-1; i = e[i].ne) { int nowjy = a[cur.id] + cur.jy; if( nowjy > k) continue; if(dis[e[i].to][nowjy]>e[i].w+cur.c) { dis[e[i].to][nowjy]=e[i].w+cur.c; pq.push(Point(e[i].to,dis[e[i].to][nowjy],nowjy)); } } }}int main() { cin>>n>>m>>k; for(int i = 1; i<=n; i++) scanf("%d",a+i); memset(head,-1,sizeof head); for(int x,y,w,i = 1; i<=m; i++) { scanf("%d%d%d",&x,&y,&w); add(x,y,w); add(y,x,w); } Dijkstra(); int ans = INF; for(int i=0; i<=k; i++) { ans=min(ans,dis[n][i]); } if(ans==INF) puts("-1"); else printf("%d\n",ans); return 0 ;}

当然你如果认准了那道“小明的贪心题”，加上这个判断也无妨（为了避免同一元素多次入队）：

#include#include#include#include#include#include#include#include#include#include#define ll long long#define pb push_back#define pm make_pairusing namespace std;const int MAX = 800 + 5;const int INF = 0x3f3f3f3f;int tot;int n,m,k;int a[MAX];int dis[MAX][15],head[MAX];struct Edge { int to,ne; int w;} e[8005];struct Point { int id; int c,jy; Point() {} Point(int id,int c,int jy):id(id),c(c),jy(jy) {} bool operator <(const Point & b) const { return c>b.c; }};void add(int u,int v,int w) { e[++tot].to = v; e[tot].w = w; e[tot].ne = head[u]; head[u] = tot;}void Dijkstra() { memset(dis,INF,sizeof dis); dis[1][0] = 0; priority_queue pq; pq.push(Point(1,0,0)); while(pq.size()) { Point cur = pq.top(); pq.pop(); if(cur.c > dis[cur.id][cur.jy]) continue; for(int i = head[cur.id]; i!=-1; i = e[i].ne) { int nowjy = a[cur.id] + cur.jy; if( nowjy > k) continue; if(dis[e[i].to][nowjy]>e[i].w+cur.c) { dis[e[i].to][nowjy]=e[i].w+cur.c; pq.push(Point(e[i].to,dis[e[i].to][nowjy],nowjy)); } } }}int main() { cin>>n>>m>>k; for(int i = 1; i<=n; i++) scanf("%d",a+i); memset(head,-1,sizeof head); for(int x,y,w,i = 1; i<=m; i++) { scanf("%d%d%d",&x,&y,&w); add(x,y,w); add(y,x,w); } Dijkstra(); int ans = INF; for(int i=0; i<=k; i++) { ans=min(ans,dis[n][i]); } if(ans==INF) puts("-1"); else printf("%d\n",ans); return 0 ;}

还可以这么写最短路这题（看起来不像是Dijkstra反倒像是bfs，但又不是bfs）：

#includeusing namespace std;struct edge { int to, next, w;} e[8100];struct node { int u, k, d; node() {} node(int u, int k, int d) : u(u), k(k), d(d) {} bool operator < (const node &a) const { return d > a.d; }};int head[888], num;int jy[888];int n, m, k;void add(int u, int v, int w) { e[num].to = v; e[num].next = head[u]; e[num].w = w; head[u] = num++;}int d[888];void Dijkstra() {//bfs memset(d, -1, sizeof d); d[1] = 0; priority_queue q; q.push(node(1, 0, 0)); while(!q.empty()) { node cur = q.top(); q.pop(); if(cur.u == n) { printf("%d\n", d[n]); return; } for(int i=head[cur.u]; i!=-1; i=e[i].next) { int v = e[i].to; if(jy[cur.u] && cur.k == k) continue; if(d[v]==-1|| d[v] > cur.d+e[i].w) { d[v] = cur.d+e[i].w; q.push(node(v,cur.k+jy[cur.u],d[v])); } } } puts("-1"); return;}int main() { memset(head, -1, sizeof head); num = 0; scanf("%d%d%d",&n,&m,&k); for(int i=1; i<=n; i++) { scanf("%d", &jy[i]); } for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：输入 输出
上一篇:戏剧性转折背后，腾讯很不简单！
下一篇:ACM技巧 - O(1)快速乘（玄学） 总结
相关文章

 发表评论

暂时没有评论，来抢沙发吧~