cogs 1254. 最难的任务 Dijkstra + 重边处理
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了cogs 1254. 最难的任务 Dijkstra + 重边处理,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1946字,纯文字阅读大概需要3分钟。
内容图文
![cogs 1254. 最难的任务 Dijkstra + 重边处理](/upload/InfoBanner/zyjiaocheng/1061/3a319232482a46d8b88403756b291c5c.jpg)
1254. 最难的任务
★ 输入文件:hardest.in
输出文件:hardest.out
简单对比
时间限制:1 s 内存限制:128 MB
【题目描述】
这个真的很难。算出 12345678987654321!,这个“!”是阶乘的意思。
呵,我在开玩笑。没有人成功的解决。
事实上,你是一个间谍。你要窃取一些敌军机密,现在你需要找到一个方法使你逃走的时间最少。
这里有很多交叉点和很多道路,在两个交叉点间可能有多条路。你很困惑,但随身携带笔记本电脑让你很快乐。
【输入格式】
第一行有一个整数T(T≤10)表示测试数据个数。
每组数据以两个整数开始,n和m(1≤n≤200,0≤m≤10000),交叉点的个数和各自的道路数。下面m行有三个整数 i,j,k(i<>j, 1≤k≤10000), 意思是i和j中间有一条长度为k的路。
你可以假设交叉点的编号为1...n。你需要从交叉点1到交叉点n。
道路是双向的。
【输出格式】
对于每组测试数据,打印最短距离。如果没有路可以出去,打印-1。
【样例输入】
1 2 1 1 2 3
【样例输出】
3
QAQ这题也太坑了吧 交了3遍才过
一共出了两个问题
1.如果无法到达 输出-1
这里有一点需要注意的是尽管memset里写的0x3f 但是实际的赋值是0x3f3f3f3f
2.有重边肿么办?
额 我用了一个神奇的方法
就是一开始把边权数组Cost全部赋值为正无穷(反正就是一个很大的数)
每次输入边权 就把边权和Cost数组里的值取一个min
(这一道题数据范围小 Cost我就开了个二维数组,太蒟了)
嗯嗯 然后我没有处理就是如果已经加入过该边就不再加了
首先这可能会很慢 每次都要从前往后猛扫一遍
其次 Dijkstra里不是有一个vis数组吗 走过一遍就不会再走了 只需要处理一下边权
使得边权保持最小就行了 Σ(⊙▽⊙"a
?(^?^*)
AC代码:
#include<bits/stdc++.h>
#define pa pair<int,int>
#define maxn 205
#define INF 0x3f3f3f3f
usingnamespace std;
int T,n,m;
bool Bian[maxn][maxn];
int Cost[maxn][maxn];
vector<int> v[maxn];
priority_queue<pa,vector<pa>,greater<pa> > q;
int dis[maxn],vis[maxn];
void Dijkstra()
{
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;
q.push(make_pair(0,1));
while(!q.empty())
{
int x=q.top().second;
q.pop();
if(vis[x])
continue;
vis[x]=1;
for(int i=0;i<v[x].size();i++)
{
int y=v[x][i];
if(dis[x]+Cost[x][y]<dis[y])
{
dis[y]=dis[x]+Cost[x][y];
q.push(make_pair(dis[y],y));
}
}
}
}
int main()
{
freopen("hardest.in","r",stdin);
freopen("hardest.out","w",stdout);
scanf("%d",&T);
while(T--)
{
memset(Cost,0x3f,sizeof(Cost));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
Cost[x][y]=Cost[y][x]=min(Cost[x][y],z);
v[x].push_back(y);//QAQ有重边到底咋办啊 v[y].push_back(x);
}
Dijkstra();
if(dis[n]==INF)
printf("-1\n");
else
printf("%d\n",dis[n]);
}
return0;
}
原文:https://www.cnblogs.com/Tidoblogs/p/11331255.html
内容总结
以上是互联网集市为您收集整理的cogs 1254. 最难的任务 Dijkstra + 重边处理全部内容,希望文章能够帮你解决cogs 1254. 最难的任务 Dijkstra + 重边处理所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。