wordpress风影,seo免费,3免费做网站,中煤第一建设公司网站P1119 灾后重建
P1119 灾后重建 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路
看数据范围知道需要用到Floyd算法#xff0c;但是道路是不能直接用的#xff0c;需要等到连接道路的两个村庄重建好才可以使用#xff0c;所以这需要按照时间依次加入中转点#xff0c…P1119 灾后重建
P1119 灾后重建 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路
看数据范围知道需要用到Floyd算法但是道路是不能直接用的需要等到连接道路的两个村庄重建好才可以使用所以这需要按照时间依次加入中转点再更新dis数组。
代码
#includebits/stdc.h
#define int long long
#define TEST int T; cin T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
const int N 1e6 30;
const int M 1e3 10;
const int inf 512785182741247112;
const int mod 100003;
using namespace std;
int f[201][201];
int n, m;
int a[201];void solve() {cin n m;for (int i 0; i n; i) cin a[i];for (int i 0; i n; i){for (int j 0; j n; j){f[i][j] inf;}}for (int i 0; i m; i){int x, y, z;cin x y z;f[x][y] f[y][x] z;}int q;cin q;int now 0;for (int i 0; i q; i){int x, y, t;cin x y t;if (a[x] t || a[y] t){cout -1\n;continue;}while (a[now] tnown){for (int j 0; j n; j){for (int k 0; k n; k){f[k][j]f[j][k] min(f[j][k], f[j][now] f[now][k]);}}now;}if (f[x][y] inf) cout -1\n;else cout f[x][y] \n;}
}
signed main() {ios;solve();return 0;
}
P6464 [传智杯 #2 决赛] 传送门
P6464 [传智杯 #2 决赛] 传送门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路
这道题需要我们使用Floyd算法因为计算全源最短路径需要三层循环但是没完枚举传送门的建设也需要两重循环五重循环必定超时所以我们需要将它优化成四重循环我们发现建设传送门时只对以传送门建设点为中转点的边有影响所以我们可以优化为四重循环。
代码
#includebits/stdc.h
#define inf 1234567890
using namespace std;
int n,m,mp1[120][120],mp2[120][120],ansinf;
void back()//返回原图
{for(int i1;in;i){for(int j1;jn;j){mp2[i][j]mp1[i][j];}}
}
int main()
{cinnm;for(int i1;in;i)for(int j1;jn;j)mp1[i][j]inf;for(int i1;im;i){int x,y,z;cinxyz;mp1[x][y]mp1[y][x]z;}for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){if(mp1[i][k]infmp1[k][j]inf)//先计算没有建立传送门的最短路径 mp1[i][j]min(mp1[i][j],mp1[i][k]mp1[k][j]);}}}for(int i1;in;i){for(int j1;jn;j){back();//每次返回原图 mp2[i][j]mp2[j][i]0;//建立传送门 for(int x1;xn;x){for(int y1;yn;y){if(mp2[x][j]infmp2[j][y]inf)mp2[x][y]min(mp2[x][y],mp2[x][j]mp2[j][y]);}}for(int x1;xn;x){for(int y1;yn;y){if(mp2[x][i]infmp2[i][y]inf)mp2[x][y]min(mp2[x][y],mp2[x][i]mp2[i][y]);}}int cnt0;for(int x1;xn;x){for(int yx1;yn;y){cntmp2[x][y];//计算最短路径和 }}ansmin(ans,cnt);//更新最小 }}coutansendl;return 0;
} P2349 金字塔
P2349 金字塔 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路
最短路模板题但是需要维护最大值一开始我将答案全部储存在dis数组里面结果只得40分
int n, m, head[N], cnt;
int mxx[N];
struct node
{int u, v, w;
}e[N];
void add(int x, int y, int z) {e[cnt].u y;e[cnt].w z;e[cnt].v head[x];head[x] cnt;
}void solve()
{cin n m;for (int i 1; i m; i) {int x, y, z;cin x y z;add(x, y, z);add(y, x, z);}vectorintdis(n 1, inf);dis[1] 0;priority_queuepllq;q.emplace(0, 1);while (q.size()) {auto it q.top();q.pop();int x it.second;for (int i head[x]; i; i e[i].v) {int now e[i].u;mxx[now] max(mxx[x], e[i].w);if (dis[now] e[i].w dis[x] mxx[now] - mxx[x]) {dis[now] e[i].w dis[x] mxx[now] - mxx[x];q.emplace(-dis[now], now);}}}cout dis[n] \n;
}
所以我们需要用两个数组来维护答案最小值dis数组和维护的边权最大值下面是AC代码。
代码
#define _CRT_SECURE_NO_WARNINGS
#includebits/stdc.h
#includealgorithm
#define int long long
#define pb push_back
#define TEST int T; cin T; while (T--)
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define lowbit(x) x(-x)
#define pll pairint,int
const int N 3e5 30;
const int M 1e3 10;
const int inf 512785182741247112;
const int mod 1e9 7;
using namespace std;
int n, m, head[N], cnt;
int mxx[N];
struct node
{int u, v, w;
}e[N];
void add(int x, int y, int z) {e[cnt].u y;e[cnt].w z;e[cnt].v head[x];head[x] cnt;
}void solve()
{cin n m;for (int i 1; i m; i) {int x, y, z;cin x y z;add(x, y, z);add(y, x, z);}vectorintdis(n 1, inf);dis[1] 0;priority_queuepllq;q.emplace(0, 1);while (q.size()) {auto it q.top();q.pop();int x it.second;for (int i head[x]; i; i e[i].v) {int now e[i].u;if (dis[now] mxx[now] e[i].w dis[x] max(e[i].w,mxx[x])) {mxx[now] max(e[i].w, mxx[x]);dis[now] e[i].w dis[x];q.emplace(-(dis[now]mxx[now]), now);}}}cout dis[n]mxx[n] \n;
}signed main() {ios;solve();return 0;
}
