58同城建网站怎么做,婚纱网站模板,网页模板代码,达浒镇网站建设公司题干#xff1a;
Island 发生了一场暴乱#xff01;现在 Rinne 要和 Setsuna 立马到地上世界去。
众所周知#xff1a;Island 是有一些奇怪的城镇和道路构成的#xff08;题目需要#xff0c;游戏党勿喷#xff09;#xff0c;有些城镇之间用双向道路连接起来了
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 1
1
0
1
0
1 2 10
2 3 10
3 1 15
1 4 60
3 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保证没有多条道路连接同一对城市也没有一条道路连向自己。
解题报告
这题可以dpdp[i][j]表示从1到 i 穿过j次戒烟戒严城镇的最短路。最近这种题见了三道了。。也可以k - 分层图。下面有好几个分层图代码建图方式和做法有所不同。也可以直接类似bfs的Dijkstra。。
AC代码1分层图
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using 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 cb.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_queuePoint 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].wcur.c) {dis[e[i].to]e[i].wcur.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 i1; in; i) scanf(%d,a[i]);for (int i1; im; i) {int x,y,w;scanf(%d%d%d,x,y,w);if(!a[x]) {for(int j 0; jk; j) add(xn*j,yn*j,w);}if(!a[y]) {for(int j 0; jk; j) add(yn*j,xn*j,w);}if(a[x]) {for(int j 0; jk; j) add(xn*j,yn*(j1),w);}if(a[y]) {for(int j 0; jk; j) add(yn*j,xn*(j1),w);} }if (k0) {printf(-1\n);return 0;}Dijkstra();int ans INF;for (int i 1; ik1; i) ansmin(ans,dis[i*n]);if (ans INF) ans -1;printf(%d\n,ans);return 0 ;
}
一个大佬的分层图
#includecstdio
#includealgorithm
#includecmath
#includecstring
using namespace std;
const int N2e510;
int a[N],he[N*10],t[N*20],ne[N*20],d[N*400],vis[N*10],tot0;
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 i1;in;i) scanf(%d,a[i]);if (a[1]) k--;if (a[n]) k;for (int i1;im;i){int x,y;long long z;scanf(%d%d%lld,x,y,z);for (int j0;jk;j){if (!a[x]) link(yn*j,xn*j,z);if (!a[y]) link(xn*j,yn*j,z);}for (int j0;jk;j){if (a[x]) link(yn*j,xn*(j1),z);if (a[y]) link(xn*j,yn*(j1),z);}}if (k0){printf(-1\n);return 0;}int i0,kk1;d[1]1;dis[1]0;for (int i2;in*(k1);i) dis[i](long long)m*40000000;i0;while (ikk){i;int ud[i];for (int jhe[u];j;jne[j]){if (dis[u]cc[j]dis[t[j]]){dis[t[j]]dis[u]cc[j];kk;d[kk]t[j];}}}long long ans(long long)m*40000000;for (int i1;ik1;i) ansmin(ans,dis[i*n]);if (ans(long long)m*40000000) ans-1;printf(%lld\n,ans);
分层图标程
#include algorithm
#include iostream
#include cstring
#include climits
#include cstdlib
#include cstdio
#include queue
#include stack
#include map
#include set
#define LL long longconst 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;}queueNode * 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
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using 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 cb.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_queuePoint 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].wcur.c) {dis[e[i].to][nowjy]e[i].wcur.c;pq.push(Point(e[i].to,dis[e[i].to][nowjy],nowjy));}}}}
int main() {cinnmk;for(int i 1; in; i) scanf(%d,ai);memset(head,-1,sizeof head);for(int x,y,w,i 1; im; i) {scanf(%d%d%d,x,y,w);add(x,y,w);add(y,x,w);}Dijkstra();int ans INF;for(int i0; ik; i) {ansmin(ans,dis[n][i]);}if(ansINF) puts(-1);else printf(%d\n,ans);return 0 ;
}
当然你如果认准了那道“小明的贪心题”加上这个判断也无妨为了避免同一元素多次入队
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using 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 cb.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_queuePoint 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].wcur.c) {dis[e[i].to][nowjy]e[i].wcur.c;pq.push(Point(e[i].to,dis[e[i].to][nowjy],nowjy));}}}}
int main() {cinnmk;for(int i 1; in; i) scanf(%d,ai);memset(head,-1,sizeof head);for(int x,y,w,i 1; im; i) {scanf(%d%d%d,x,y,w);add(x,y,w);add(y,x,w);}Dijkstra();int ans INF;for(int i0; ik; i) {ansmin(ans,dis[n][i]);}if(ansINF) puts(-1);else printf(%d\n,ans);return 0 ;
}
还可以这么写最短路这题看起来不像是Dijkstra反倒像是bfs但又不是bfs
#includebits/stdc.h
using 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() {//bfsmemset(d, -1, sizeof d);d[1] 0;priority_queuenode 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 ihead[cur.u]; i!-1; ie[i].next) {int v e[i].to;if(jy[cur.u] cur.k k) continue;if(d[v]-1|| d[v] cur.de[i].w) {d[v] cur.de[i].w;q.push(node(v,cur.kjy[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 i1; in; i) {scanf(%d, jy[i]);}for(int i0; im; i) {int u, v, w;scanf(%d%d%d,u,v,w);add(u,v,w);add(v,u,w);}Dijkstra();
}
