当前位置：首页 > 芯闻号 > 充电吧

HDU 2112 HDU Today （最短路）

时间：2019-11-25 15:06:01
关键字： 最短路    迪杰斯特拉   
手机看文章

扫描二维码
随时随地手机看文章

[导读]题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2112 题面： HDU Today Time Limit: 15000/5000 MS (Java

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2112


题面：

HDU Today Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 20504    Accepted Submission(s): 4835


Problem Description 经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候，XHD夫妇也退居了二线，并在风景秀美的诸暨市浬浦镇陶姚村买了个房子，开始安度晚年了。
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。
徐总经常会问蹩脚的英文问路：“Can you help me?”。看着他那迷茫而又无助的眼神，热心的你能帮帮他吗？
请帮助他用最短的时间到达目的地（假设每一路公交车都只在起点站和终点站停，而且随时都会开）。
 
Input 输入数据有多组，每组的第一行是公交车的总数N(0<=N<=10000)；
第二行有徐总的所在地start，他的目的地end；
接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0 note：一组数据中地名数不会超过150个。
如果N==-1，表示输入结束。
 
Output 如果徐总能到达目的地，输出最短的时间；否则，输出“-1”。
 
Sample Input 
6
xiasha westlake
xiasha station 60
xiasha ShoppingCenterofHangZhou 30
station westlake 20
ShoppingCenterofHangZhou supermarket 10
xiasha supermarket 50
supermarket westlake 10
-1


 


Sample Output


50


Hint:
The best route is:
xiasha->ShoppingCenterofHangZhou->supermarket->westlake


虽然偶尔会迷路，但是因为有了你的帮助
**和**从此还是过上了幸福的生活。

――全剧终――


 


Author

lgx

 


题目大意：



    求从A到B的最短路。





解题：


    用map映射下标，建立图然后求最短距离即可。





坑点：


   1.注意重边，有重边取最小值。


   2.起点终点可能相同，这里可能会错。


   3.起点被孤立，小心死在里面，造成RE。


   4.双向边，坑了我好久/(ㄒoㄒ)/~~





代码：




#include 
#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
using namespace std;
int mapp[200][200],dist[200];
bool vis[200];
void init()
{
    for(int i=0;i<200;i++)
        for(int j=0;j<200;j++)
         {
            if(i==j)
              mapp[i][i]=0;
            else
              mapp[i][j]=inf;
         }
    for(int i=0;i<200;i++)
      dist[i]=inf;
    memset(vis,0,sizeof(vis));
}
void dijkstra(int s,int n)
{
   int minn=inf,p=0,tmp;
   for(int i=0;i<=n;i++)
   {
     if((i!=s)&&mapp[s][i] refl;
int main()
{
	int n,cnt,val,f,t;
	string sta,des,fm,to;
	while(cin>>n)
	{
	   cnt=0;
	   if(n==-1)break;
	   refl.clear();
	   cin>>sta>>des;
	   refl[sta]=0;
	   init();
	   dist[0]=0;
	   for(int i=0;i>fm>>to>>val;
	       if(refl.count(fm))
	         f=refl[fm];
           else
           {
              refl[fm]=++cnt;
              f=cnt;
           }
           if(refl.count(to))
             t=refl[to];
           else
           {
             refl[to]=++cnt;
             t=cnt;
           }
           if(val


        

                
        

                                     
        

                            
本站声明： 本文章由作者或相关机构授权发布，目的在于传递更多信息，并不代表本站赞同其观点，本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者，如若文章内容侵犯您的权益，请及时联系本站删除。

        
        

            
        


        


        

        
            

                

                    

                        
                        换一批
                    

                    
延伸阅读

                

                                

                                                                            

                                    
[通信先锋]
                                        
阿维塔、赛力斯已入股！华为引望可能成“中国博世”

                                    

                                    

                                                                                
                                        
                                        
                                        
                                        
                                                                                
9月2日消息，不造车的华为或将催生出更大的独角兽公司，随着阿维塔和赛力斯的入局，华为引望愈发显得引人瞩目。

                                        关键字：
								                                    阿维塔
                                                                    塞力斯
                                                                    华为
                                							
                                    

                                

                                                                                                        

                                    
[美通社全球TMT]
                                        
Trianz与AWS达成战略合作协议，彻底改变云采用和管理方式

                                    

                                    

                                                                                
                                        
                                        
                                        
                                        
                                                                                
                       加利福尼亚州圣克拉拉县2024年8月30日 /美通社/ -- 数字化转型技术解决方案公司Trianz今天宣布，该公司与Amazon Web Services （AWS）签订了...

                                        关键字：
								                                    AWS
                                                                    AN
                                                                    BSP
                                                                    数字化
                                							
                                    

                                

                                                                                                        

                                    
[美通社全球TMT]
                                        
人工智能驱动工具SODA V将颠覆汽车市场，使汽车开发时间和成本降低90%

                                    

                                    

                                                                                
                                        
                                        
                                        
                                        
                                                                                
伦敦2024年8月29日 /美通社/ -- 英国汽车技术公司SODA.Auto推出其旗舰产品SODA V，这是全球首款涵盖汽车工程师从创意到认证的所有需求的工具，可用于创建软件定义汽车。 SODA V工具的开发耗时1.5...

                                        关键字：
								                                    汽车
                                                                    人工智能
                                                                    智能驱动
                                                                    BSP
                                							
                                    

                                

                                                                                                        

                                    
[美通社全球TMT]
                                        
从容应对未知风险----解密亚马逊云科技的韧性之道

                                    

                                    

                                                                                
                                        
                                        
                                        
                                        
                                                                                
北京2024年8月28日 /美通社/ -- 越来越多用户希望企业业务能7×24不间断运行，同时企业却面临越来越多业务中断的风险，如企业系统复杂性的增加，频繁的功能更新和发布等。如何确保业务连续性，提升韧性，成...

                                        关键字：
								                                    亚马逊
                                                                    解密
                                                                    控制平面
                                                                    BSP
                                							
                                    

                                

                                                                                                        

                                    
[通信先锋]
                                        
中国游戏市场开始复苏！腾讯、网易等巨头缩减在日本投资

                                    

                                    

                                                                                
                                        
                                        
                                        
                                        
                                                                                
8月30日消息，据媒体报道，腾讯和网易近期正在缩减他们对日本游戏市场的投资。

                                        关键字：
								                                    腾讯
                                                                    编码器
                                                                    CPU
                                							
                                    

                                

                                                                                                        

                                    
[通信先锋]
                                        
独立自主！华为董事：致力打造不依赖西方的技术

                                    

                                    

                                                                                
                                        
                                        
                                        
                                        
                                                                                
8月28日消息，今天上午，2024中国国际大数据产业博览会开幕式在贵阳举行，华为董事、质量流程IT总裁陶景文发表了演讲。

                                        关键字：
								                                    华为
                                                                    12nm
                                                                    EDA
                                                                    半导体
                                							
                                    

                                

                                                                                                        

                                    
[通信先锋]
                                        
华为张平安：数字世界话语权最终由生态繁荣决定！

                                    

                                    

                                                                                
                                        
                                        
                                        
                                        
                                                                                
8月28日消息，在2024中国国际大数据产业博览会上，华为常务董事、华为云CEO张平安发表演讲称，数字世界的话语权最终是由生态的繁荣决定的。

                                        关键字：
								                                    华为
                                                                    12nm
                                                                    手机
                                                                    卫星通信
                                							
                                    

                                

                                                                                                        

                                    
[美通社全球TMT]
                                        
中国通信服务公布2024年中期业绩

                                    

                                    

                                                                                
                                        
                                        
                                        
                                        
                                                                                
要点：     有效应对环境变化，经营业绩稳中有升   落实提质增效举措，毛利润率延续升势   战略布局成效显著，战新业务引领增长   以科技创新为引领，提升企业核心竞争力   坚持高质量发展策略，塑强核心竞争优势...

                                        关键字：
								                                    通信
                                                                    BSP
                                                                    电信运营商
                                                                    数字经济
                                							
                                    

                                

                                                                                                        

                                    
[美通社全球TMT]
                                        
NVI技术创新联盟成立！自主生态将带动产业链高速发展

                                    

                                    

                                                                                
                                        
                                        
                                        
                                        
                                                                                
北京2024年8月27日 /美通社/ -- 8月21日，由中央广播电视总台与中国电影电视技术学会联合牵头组建的NVI技术创新联盟在BIRTV2024超高清全产业链发展研讨会上宣布正式成立。  活动现场  NVI技术创新联...

                                        关键字：
								                                    VI
                                                                    传输协议
                                                                    音频
                                                                    BSP
                                							
                                    

                                

                                                                                                        

                                    
[美通社全球TMT]
                                        
软通动力与长三角投资达成战略合作 共谋数字生态新发展

                                    

                                    

                                                                                
                                        
                                        
                                        
                                        
                                                                                
北京2024年8月27日 /美通社/ -- 在8月23日举办的2024年长三角生态绿色一体化发展示范区联合招商会上，软通动力信息技术（集团）股份有限公司（以下简称"软通动力"）与长三角投资（上海）有限...

                                        关键字：
								                                    BSP
                                                                    信息技术
                                							
                                    

                                

                                                                


                
                
                

            

            

    






    关闭
    







	

	

	





    
    

        关闭