【洛谷 2299】Mzc和体委的争夺战

题目背景

ｍｚｃ与ｄｊｎ第四弹。

题目描述

mzc家很有钱（开玩笑），他家有n个男家丁（做过前三弹的都知道）。但如此之多的男家丁吸引来了我们的体委（矮胖小伙），他要来与mzc争夺男家丁。

mzc很生气，决定与其决斗，但cat的体力确实有些不稳定，所以他需要你来帮他计算一下最短需要的时间。

输入输出格式

输入格式：

第一行有两个数n,m.n表示有n个停留站，m表示共有m条路。

之后m行，每行三个数aibicia_i \; b_i \; c_iai​bi​ci​，表示第aia_iai​个停留站到第bib_ibi​个停留站需要cic_ici​的时间。（无向）

输出格式：

一行，输出1到n最短时间。

输入输出样例

输入样例#1： 复制 5 8 1 2 3 2 3 4 3 4 5 4 5 6 1 3 4 2 4 7 2 5 8 1 5 100 输出样例#1： 复制 11

说明

n≤2500m≤2∗105n \leq 2500\;m \leq 2*10^5n≤2500m≤2∗105

由于mzc大大十分着急，所以他只能等待1s。

 

题解：真-dijkstra，最短路+邻接矩阵

#include<bits/stdc++.h> #include<iostream> #include<algorithm> #include<queue> #include<cmath> #include<cstring> #include<cstdlib> #include<cstdio> using namespace std; int a[2501][2501],vis[10001],dis[10001]; int main(){ //freopen("2299.in","r",stdin); //freopen("2299.out","w",stdout); memset(a,0x3f,sizeof(a)); int n,m; cin>>n>>m; for(int i=1;i<=m;i++){ int x,y,z; cin>>x>>y>>z; if(z<a[x][y]){ a[x][y]=z; a[y][x]=z; } } for(int i=1;i<=n;i++) dis[i]=a[1][i]; dis[1]=0; for(int i=1;i<=n;i++) { int k=0; int minn=0x3f3f3f3f; for(int j=1;j<=n;j++){ if(vis[j]==0&&dis[j]<minn){ minn=dis[j]; k=j; } } if(k==0) break; vis[k]=1; for(int j=1;j<=n;j++) if(dis[k]+a[k][j]<dis[j]) dis[j]=dis[k]+a[k][j]; } cout<<dis[n]; return 0; }

 

转载于:https://www.cnblogs.com/wuhu-JJJ/p/11126222.html

相关资源：各显卡算力对照表！