求最短路。。。 要多水就有多水,刷水的感觉很差,很少用SPFA,所以算是练习下SPFA把。。
传送门:http://lightoj.com/volume_showproblem.php?problem=1019
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
const int MAXN = 111;
int inQ[MAXN],dist[MAXN],t,n,m;
vector<pair<int,int> > g[MAXN];
void init(){
fill(dist,dist+MAXN,0x3fffffff);
memset(inQ,0,sizeof(inQ));
for(int i=0;i<MAXN;i++)g[i].clear();
}
int SPFA(int src,int dest){
queue<int> Q;
Q.push(src);
inQ[src] = 1;
dist[src] = 0;
while(!Q.empty()){
int now = Q.front();
Q.pop();inQ[now] = 0;
for(int i=0;i<(int)g[now].size();i++){
//cout<<now<<" "<<v<<" "<<val[v]<<endl;
int v = g[now][i].first,w = g[now][i].second;
if(dist[v]>dist[now]+w){
dist[v] = dist[now]+w;
if(!inQ[v]){
inQ[v] = 1;
Q.push(v);
}
}
}
}
return dist[dest];
}
int main(){
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
scanf("%d%d",&n,&m);init();
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a].push_back(make_pair(b,c));
g[b].push_back(make_pair(a,c));
}
int d = SPFA(1,n);
if(d!=0x3fffffff)
printf("Case %d: %d\n",cas,d);
else
printf("Case %d: Impossible\n",cas);
}
return 0;
}
分享到:
相关推荐
LightOJ-已解决代码我所有的Light Online Judge的解决问题代码。
轻描淡写 像Codeforces编辑模式一样在lightoj上发表社论!
LightOJ-solutions
LightOJ
leetcode中国 数据结构和算法编码 议程 :balloon: 不是为了比赛,而是为了训练和兴趣。 Python3 你可以在这里找到我的 LeetCode 解决方案:(等待打开) ...LightOJ 1012 --- dfs transform 13. HDU 1495 --- compl
解析编程问题,并将其发送给CHelper插件以实现IntelliJ IDEA。 竞争性伴侣解析程序...-HackerRank-HDU在线法官-Kattis-LightOJ-NYTD在线法官-PEG法官-POJ-QDUOJ-Timus-URI在线法官 支持语言:English (United States)
问题教程:一个包含有关LightOJ问题的教程的存储库
leetcode 2 和 c 动态规划 动态规划相关问题的解答。 这些问题来自各种在线评委,包括 、 、 等。 解决方案是用 C++ 编码的。 —— —— —— —— —— —— —— —— —— —— —— —— ...——
光OJ 收集我在发现的一些问题的解决方案
已解决的编程问题 Online Judges 这个存储库包含我解决的各种在线法官的编程问题的解决方案,即 UVa、Topcoder、Codeforces、Hackerrank、LightOj、Spoj、Project Euler 等。
这是乔杜里医学博士。 伊斯玛姆·拉赫曼(Ishmam Rahman) :closed_mailbox_with_raised_flag: 联络我: ... LightOJ: ://lightoj.com/user/ishmam64 脸书: : 目标:使自己在新技术的海洋中立足,在这里我可
描述在这里,您可以从uva,lightoj,spoj,timus等不同的在线法官那里找到我解决的问题。
这个仓库是关于什么的 创建该存储库是为了组织与数据结构和算法有关的问题的解决方案。 并且,如果可能的话,为学习与数据结构和算法有关的各种概念提供一种更简单的方法。 以下评委使用的问题 ...
race_words = [“后缀数组”,“前缀特里”,“动态编程”,“竞赛”,“ codeforces”,“编程”,“竞争性编程”,“算法”,“数据结构”,“ codeforces”,“ light oj”,“ lightoj”,“ spoj”,“堆栈”,...
开心农场java源码AA Noman Ansary 你好呀! 我的名字是AA Noman Ansary 。 但我更喜欢被称为Showrav...问题解决:LightOJ。 代码部队。 蒂姆斯。 紫外线。 成就 以下是我的一些显著成就: BRAC 大学副校长证书。 (2019)
测试程序TestProgram 是针对竞争性编程程序(即 Codeforces、lightOJ、OmegaUp 等)的专用测试工具。 当我们解决问题时,我们必须非常小心,并致力于解决所有可能的情况。 我们的解决方案在登顶前正确解决的测试用例...
problemSolving