网站推广的基本方式,大连网页制作培训,做新浪网网站所需的条件,ps网站建设要知道的知识题干#xff1a;
Alice和Bob现在要乘飞机旅行#xff0c;他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务#xff0c;设这些城市分别标记为0到n-1#xff0c;一共有m种航线#xff0c;每种航线连接两个城市#xff0c;并且航线有一定的价格。Alice和…题干
Alice和Bob现在要乘飞机旅行他们选择了一家相对便宜的航空公司。该航空公司一共在n个城市设有业务设这些城市分别标记为0到n-1一共有m种航线每种航线连接两个城市并且航线有一定的价格。Alice和Bob现在要从一个城市沿着航线到达另一个城市途中可以进行转机。航空公司对他们这次旅行也推出优惠他们可以免费在最多k种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少
Input
数据的第一行有三个整数n,m,k分别表示城市数航线数和免费乘坐次数。
第二行有两个整数s,t分别表示他们出行的起点城市编号和终点城市编号。(0s,tn)
接下来有m行每行三个整数a,b,c表示存在一种航线能从城市a到达城市b或从城市b到达城市a价格为c。(0a,bn,a与b不相等0c1000) Output 只有一行包含一个整数为最少花费。
Sample Input
5 6 1 0 4 0 1 5 1 2 5 2 3 5 3 4 5 2 3 3 0 2 100
Sample Output
8
Hint 对于30%的数据,2n50,1m300,k0; 对于50%的数据,2n600,1m6000,0k1; 对于100%的数据,2n10000,1m50000,0k10. 解题报告 注意一下数据范围k10所以你需要乘以11这题控制不好数据范围很容易就RE了、、、
AC代码
#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 INF 0x3f3f3f3f;
const int MAXN 10000 5;
const int MAXM 50000 5;
struct edge {int to, ne;int w;
} e[MAXM*4*11];
struct node {int u, c;node() {}node(int u, int c) : u(u), c(c) {}bool operator (const node a) const {return c a.c;}
};
int head[MAXN*11], tot;
int dis[MAXN*11];
bool vis[MAXN*11];
int n, m, k;
int st,ed;
void add(int u, int v, int w) {e[tot].to v;e[tot].ne head[u];e[tot].w w;head[u] tot;
}void Dijkstra(int st) {memset(dis, INF, sizeof dis);dis[st] 0;priority_queuenode pq;pq.push(node(st, 0));while(!pq.empty()) {node cur pq.top(); pq.pop();if(vis[cur.u]) continue;vis[cur.u] 1;for(int ihead[cur.u]; i!-1; ie[i].ne) {int v e[i].to;if(dis[v] cur.ce[i].w) {dis[v] cur.ce[i].w;pq.push(node(v,dis[v]));}}}
}
int main()
{memset(head, -1, sizeof head);tot 0;scanf(%d%d%d,n,m,k);cinsted;for(int i1; im; i) {int u, v, w;scanf(%d%d%d,u,v,w);for(int j 0; jk; j) {add(uj*n,vj*n,w);add(vj*n,uj*n,w);}for(int j 0; jk; j) {add(uj*n,v(j1)*n,0);add(vj*n,u(j1)*n,0);}}Dijkstra(st);int ans INF;for(int j 0; jk; j) {//不用~用k次一共k1个图 ans min(ans,dis[j*ned]); }printf(%d\n,ans);return 0 ;
}建立分层图的代码
for(int i1; im; i) {scanf(%d%d%d,a,b,c);for(int j0; jk; j) {add(aj*n,bj*n,c);add(bj*n,aj*n,c);if(jk) {add(aj*n,b(j1)*n,0);add(bj*n,a(j1)*n,0);}}
}
我们有k次免费坐飞机的机会那么就有k1个图 我们只要保证我们每一次创建的图满足i*na当前位置的标号。 20190508更新最短路dp的做法。
还WA了一发因为写着写着就忘了是双向边了。
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
const int INF 0x3f3f3f3f;
int dis[10005][12];
bool vis[10005][12];
int head[MAX],tot;
int n,m,k,st,ed;
struct Edge {int to,ne,w;
} e[MAX];
void add(int u,int v,int w) {e[tot].to v;e[tot].ww;e[tot].nehead[u];head[u] tot;
}
struct Point {int pos,ci,c;Point(int pos0,int ci0,int c0):pos(pos),ci(ci),c(c){}bool operator(const Point b)const {return c b.c;}
};
void Dijkstra() {priority_queuePoint pq;for(int i 1; in; i) {for(int j 0; jk; j) dis[i][j]INF,vis[i][j]0;}dis[st][0]0;pq.push(Point(st,0,0));while(pq.size()) {Point cur pq.top();pq.pop();if(cur.pos ed) break;if(vis[cur.pos][cur.ci]) continue;vis[cur.pos][cur.ci] 1;for(int i head[cur.pos]; ~i; i e[i].ne) {int v e[i].to;if(vis[v][cur.ci] 0) {if(dis[v][cur.ci] dis[cur.pos][cur.ci] e[i].w) {dis[v][cur.ci] dis[cur.pos][cur.ci] e[i].w;pq.push(Point(v,cur.ci,dis[v][cur.ci]));}}int tmpci cur.ci1;if(tmpci k) continue;if(vis[v][tmpci] 0) {if(dis[v][tmpci] dis[cur.pos][cur.ci]) {dis[v][tmpci] dis[cur.pos][cur.ci];pq.push(Point(v,tmpci,dis[v][tmpci]));}}} }
}
int main()
{cinnmk;cinsted;st,ed;for(int i 1; in1; i) head[i] -1;for(int a,b,c,i 1; im; i) {scanf(%d%d%d,a,b,c);a,b;add(a,b,c);add(b,a,c);}Dijkstra();int ans INF;for(int i 0; ik; i) {ans min(ans,dis[ed][i]);}printf(%d\n,ans);return 0 ;
}
//21:20 - 21:39
