c++|极其简单的最短路_纪中2051_spfa
题目描述
小C终于被小X感动了，于是决定与他看电影，然而小X距离电影院非常远，现在假设每条道路需要花费小X的时间为1，由于有数以万计的好朋友沿路祝贺，导致小X在通过某些路不得不耗费1的时间来和他们聊天，尽管他希望尽早见到小C，所以他希望找到一条最快时间到达电影院的路。
一开始小X在1号点，共有N个点，M条路，电影院为T号点。
输入 第一行3个正整数，分别为n，m，t
以下m行，每行3个数，表示连接的编号以及权值
（注意，可能会有重边）
输出 一行一个数，表示1到t的最短路
数据范围 【c++|极其简单的最短路_纪中2051_spfa】30%：n<=10 m<=20
60%: n<=1000 m<=20000
100%: n<=5000000 m<=10000000
题解 题目已经这么直白了还有什么好说|-_-|
直接连边、跑一遍spfa就可以了
数据太水？反正第一次数组开小但还是过了还是最快的
码
#include
#include
using namespace std;
struct edge
{
int x,y,w,next;
};
queueq;
edge e[20000001];
bool v[5000001];
int ls[20000001],dis[5000001];
int maxE=0;
void add(int x,int y,int w)
{
e[++maxE]=(edge){x,y,w,ls[x]};
ls[x]=maxE;
}
int main()
{
freopen("short.in","r",stdin);
freopen("short.out","w",stdout);
int n,m,ed;
scanf("%d%d%d",&n,&m,&ed);
for (int i=1;
i<=n;
i++)
dis[i]=1<<30;
dis[1]=0;
for (int i=1;
i<=m;
i++)
{
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
add(y,x,w);
}
q.push(1);
while (!q.empty())
{
int now=q.front();
q.pop();
for (int i=ls[now];
i;
i=e[i].next)
if (e[i].w+dis[now] 推荐阅读
- 科学养胃，别被忽悠，其实真的很简单
- opencv|opencv C++模板匹配的简单实现
- 松软可口易消化，无需烤箱超简单，新手麻麻也能轻松成功~
- C语言学习|第十一届蓝桥杯省赛 大学B组 C/C++ 第一场
- 简单心理2019春A期+32+张荣
- 《算法》-图[有向图]
- android防止连续点击的简单实现（kotlin）
- 机器学习一些简单笔记
- Android超简单实现沉浸式状态栏
- c++基础概念笔记