首页 > 其他分享 >无题 (最短路)

无题 (最短路)

时间:2023-04-20 15:09:14浏览次数:40  
标签:head Atiq int 短路 vis edge 无题 dis


无题

Description



Tanvir returned home from the contest and got angry after seeing his room dusty. Who likes to see a dusty room after a brain storming programming contest? After checking a bit he found that there is no brush in him room. So, he called Atiq to get a brush. But as usual Atiq refused to come. So, Tanvir decided to go to Atiq's house.

The city they live in is divided by some junctions. The junctions are connected by two way roads. They live in different junctions. And they can go to one junction to other by using the roads only.

Now you are given the map of the city and the distances of the roads. You have to find the minimum distance Tanvir has to travel to reach Atiq's house.


Input



Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a blank line. The next line contains two integers N (2 ≤ N ≤ 100) and M (0 ≤ M ≤ 1000), means that there are N junctions and M two way roads. Each of the next M lines will contain three integers u v w (1 ≤ u, v ≤ N, w ≤ 1000), it means that there is a road between junction u and v and the distance is w. You can assume that Tanvir lives in the 1st junction and Atiq lives in the Nth junction. There can be multiple roads between same pair of junctions.


Output



For each case print the case number and the minimum distance Tanvir has to travel to reach Atiq's house. If it's impossible, then print'Impossible'.


Sample Input



2

 

3 2

1 2 50

2 3 10

 

3 1

1 2 40


Sample Output



Case 1: 60

Case 2: Impossible

#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
struct Edge
{
	int from,to,val,next;
}edge[2100];
int head[1010],edgenum;
void add(int u,int v,int w)
{
	Edge E={u,v,w,head[u]};
	edge[edgenum]=E;
	head[u]=edgenum++;
}
int n;
int dis[110],vis[110];
void SPFA(int x)
{
	queue<int>q;
	memset(vis,0,sizeof(vis));
	memset(dis,INF,sizeof(dis));
	q.push(x);
	dis[x]=0;
	vis[x]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			int v=edge[i].to;
			if(dis[v]>dis[u]+edge[i].val)
			{
				dis[v]=dis[u]+edge[i].val;
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	if(dis[n]==INF)
		printf("Impossible\n");
	else
		printf("%d\n",dis[n]);
}
int main(){
	int t,m,s=0;
	scanf("%d",&t);
	while(t--)
	{
		int a,b,c;
		scanf("%d%d",&n,&m);
		memset(head,-1,sizeof(head));
		edgenum=0;
		while(m--)
		{
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,c);
			add(b,a,c);
		}
		printf("Case %d: ",++s);
		SPFA(1);
	}
	return 0;
}



标签:head,Atiq,int,短路,vis,edge,无题,dis
From: https://blog.51cto.com/u_16079508/6209561

相关文章

  • 迷宫最短路径
    定义一个二维数组: intmaze[n][m]; 它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。intmaze[6][7]={0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,0,0,1,0,1,......
  • 讲课:拓扑排序、最短路算法
    什么是图?把图在计算机中表示(储存)拓扑排序度与一个顶点v关联的边的条数称作该顶点的度(degree)在有向图G=(V,E)中,以一个顶点v为起点的边的条数称为该顶点的出度(out-degree),以一个顶点v为终点的边的条数称为该节点的入度(in-degree)思路首先记录各......
  • free (牛客多校) (dj最短路+dp优化处理)
    本题大意:给出n,m,s,t,k,n个点,m条路,求s到t的最短路,并且最多k条路免费,然后给出m行,u,v,w,代表u到v有一条权值为w的双向路。 思路:就是dj最短路+一个dp维度的处理,dp[i][j],到第i个节点用了多少个免费的路径的最短路径 ......
  • 最短路合辑
    Dijkstra算法,堆优化版本复杂度是mlog(m)。适合于没有负权的图。#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;constintN=1e5+5;constintINF=0x3f3f3f3f;vector<pair<int,int>>G[N];intvis[N];intdist[N];voiddij(ints){......
  • 2642. 设计可以求最短路径的图类
    题目链接:2642.设计可以求最短路径的图类方法一:Dijkstra解题思路每次调用\(shortestPath(st,ed)\)时,就通过\(Dijkstra\)算法计算\(st\)->\(ed\)的最短路。代码朴素写法classGraph{private:vector<vector<int>>adj;inte[110][110],n;public:G......
  • Dijkstra算法求最短路
    一、Dijkstra 只适用于单源最短路中所有边权都是正数的情况二、存储方式1、稠密图用邻接矩阵2、稀疏图用邻接表三、算法实现用一个dist数组保存源点到其余各个节点的距离,dist[i]表示源点到节点i的距离。将dist数组赋值为正无穷,dist[1]=0用......
  • UVA 12295 Optimal Symmetric Paths 最短路求方案数
    题目:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=23587题意:给一个n*n的矩阵,每个方格中有一个数字,从左上角走到右下角,且路径必须关于副对角线对称,求使路线上数字和最小的方案数思路:既然要关于副对角线对称,那么可以把关于副对角线对称的方格的值加到一起去,这样就......
  • LeetCode 周赛 340,质数 / 前缀和 / 极大化最小值 / 最短路 / 平衡二叉树
    本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]提问。大家好,我是小彭。上周跟大家讲到小彭文章风格的问题,和一些朋友聊过以后,至少在算法题解方面确定了小彭的风格。虽然竞赛算法题的文章受众非常小,但却有很多像我一样的初学者,他们有兴趣参加但容易被题目难......
  • Codeforces Round #303 (Div. 2) E. Paths and Trees (最短路+变形最小生成树)
    题目地址:E.PathsandTrees模拟了一场CF,这场实在太水了。。边玩边做的。。最后半分钟交了一发E题。。不幸AK绝杀失败。。。。首先的思路肯定是先求最短路,把可能为最短路的边挑出来,然后第二步我本来写的是直接用无向图的最小生成树,于是绝杀失败。。。后来才发现这样是不行的。......
  • (CCPC F题)UESTC 1220 The Battle of Guandu (最短路)
    题目地址:UESTC1220比赛的时候翻译完想了一小会就没再管。结果K题也没调试出来。。这题是很神奇的图论题,建图方式是从y[i]到x[i]连一条有向边,权值为c[i]。然后将所有重要性为0的设为源点,然后跑最短路,结果就是所有重要性为2的点的最短距离。实在是不好解释和证明这种建图的正......