A solo trip

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 23391    Accepted Submission(s): 8140

Problem Description
Although cao'er is a road maniac ( I have been in Hangdian for more than a year . Even people who get lost on campus , Khan, ~), But cao'er still likes traveling very much , Because on the journey I'm going to meet a lot of people ( Prince charming ,^0^), A lot of things , And enrich your own experience , You can also see beautiful scenery …… Cao Er wants to go to many places , She wants to see the night view of the Tokyo Tower . Going to Venice to see a movie , Go to Yangming Mountain to see taro , Go to New York to see the snow , Go to Paris for coffee and write letters , Visit Meng Jiangnu in Beijing …… Winter vacation is coming , For such a long time , It can't be wasted , Be sure to give yourself a good holiday . But we can't neglect the training , So Cao Er decided to go to a place he wanted to go in the shortest time ! Because Cao er's home is in a small town , There is no train passing by , So she can only go to the neighboring cities by train ( What a pity ~).
 
Input
Multiple groups of input data , The first line of each group is three integers T,S and D. Express T Strip road , The cities adjacent to Caoer's home are S individual , Where grass wants to go is D individual ;

Then there was T That's ok . There are three integers on each line a,b,time, Express a,b The distance between cities is time Hours ;(1=<(a,b)<=1000;a,b There may be multiple paths between them )

The next step is T+1 Yes S Number , It means the city connected with cao'er's family .

The next step is T+2 Yes D Number , Where does Cao Er want to go .

 
Output
The shortest time that output grass can go to a favorite city .
 
Sample Input
6 2 3
1 3 5
1 4 7
2 8 12
3 8 4
4 9 12
9 10 2
1 2
8 9 10
 
Sample Output
9
 
Author
Grass
 
Source
 
Recommend
 

Shortest path problem , There is no negative value ,dijkstra Algorithm , Priority queue implementation

Find the shortest path step
The algorithm process is as follows :
G={V,E}
1. The initial season S={V0},T=V-S={ The rest of the vertices },T The distance value corresponding to the vertex in
If exist <V0,Vi>,d(V0,Vi) by <V0,Vi> The weight on the arc
If it does not exist <V0,Vi>.d(V0,Vi) by ∞
2. from T Choose one of the following from S The vertex with the least weight and associated edge in the W, Add to S in
3. For the rest T Change the distance value of the vertex in : If you add W Make the middle vertex . from V0 To Vi The distance value of is shortened , Then change the distance value
Repeat the above steps 2、3, until S All vertices are included in . namely W=Vi until

dijkstra The idea is in this picture

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast" alt="">

Attach code :

#include <stdio.h>
#include <string.h>
#include <queue>
#define inf 0x3fffffff
using namespace std;
int map[1005][1005],vis[1005],min_road,max_road;
struct node
{
int time,pos;
friend bool operator<(node a,node b)
{
return a.time>b.time;
}
};
priority_queue<node>S;
int dijkstra(int star,int end)
{
node temp;
int x=inf;
temp.pos=star,temp.time=0;
S.push(temp);
while(!S.empty())
{
node temp1;
temp1=temp=S.top();
S.pop();
vis[temp.pos]=1;
if(temp.pos==end)
{
x=temp.time;
break;
}
for(int i=min_road;i<=max_road;i++)
{
if(!vis[i]&&map[temp.pos][i]<1000000)
{
temp.time=map[temp.pos][i]+temp.time;
temp.pos=i;
S.push(temp);
}
temp=temp1;
}
} return x;
}
int main()
{
int t,s,d;
while(scanf("%d %d %d",&t,&s,&d)!=EOF)
{
min_road=inf,max_road=-inf;
memset(map,100,sizeof(map));
for(int i=0;i<t;i++)
{
int a,b,time;
scanf("%d %d %d",&a,&b,&time);
if(map[a][b]>time)// There may be multiple paths to choose the smallest
map[a][b]=map[b][a]=time;
if(a>max_road)//max_road,min_road Just to shorten the time
max_road=a;
if(b>max_road)
max_road=b;
if(a<min_road)
min_road=a;
if(b<min_road)
min_road=b;
}
int star[1005],min_time=inf;
memset(star,0,sizeof(star));
for(int i=0;i<s;i++)
scanf("%d",&star[i]);
for(int i=0;i<d;i++)
{
int end;
scanf("%d",&end);
for(int j=0;j<s;j++)
{
while(!S.empty())
S.pop();
memset(vis,0,sizeof(vis));
int temp=dijkstra(star[j],end);
if(min_time>temp)
min_time=temp;
}
}
printf("%d\n",min_time);
}
return 0;
}

hdu 2066 A solo trip (dijkstra) More articles about

  1. hdu 2066 A solo trip Dijkstra

    Topic link :http://acm.hdu.edu.cn/showproblem.php?pid=2066 Problem analysis : Take Caoer family as the starting point , Give the time of arrival between cities , Give the city that cao'er wants to go to , The shortest time . A typical single source is the most ...

  2. HDU 2066 A solo trip (Dijkstra Algorithm )

    A solo trip Time Limit : 1000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other) Total Submis ...

  3. hdu 2066 A solo trip

    Topic linking http://acm.hdu.edu.cn/showproblem.php?pid=2066 A solo trip Description Although cao'er is a road maniac ( I have been in Hangdian for more than a year , I'm still crazy on campus ...

  4. HDU 2066 A solo trip (dijkstra Water problem + Judge heavy side )

    Topic link :http://acm.hdu.edu.cn/showproblem.php?pid=2066 The main idea of the topic : Multiple groups of input data , The first line of each group is three integers T,S and D, Express T Strip road , The cities adjacent to Caoer's home are ...

  5. HDU 2066 A solo trip 【Dijkstra 】

    The question : give s A starting point ,d It's a destination , Ask the shortest distance from the beginning to the end Because there are many starting points , So set the values of these starting points to 0 Ah = = I've changed it for a long time = = Because it's in the code t, I don't know why to call dijkstra() After the function ...

  6. hdu 2066 A solo trip Problem solving report

    Topic link :http://acm.hdu.edu.cn/showproblem.php?pid=2066 The title mean : give T Strip road , The city number adjacent to Caoer's house , And the number of the place where grass wants to go . What do you want to go from Caoer's home to Caoer's ...

  7. hdu - 2066 A solo trip ( The shortest path of the foundation )

    http://acm.hdu.edu.cn/showproblem.php?pid=2066 The shortest distance between the city and grass is 0, Then proceed dijkstra, stay t You can find the nearest one among the cities . #inc ...

  8. HDU 2066 A solo trip - from lanshui_Yang

    Problem Description Although cao'er is a road maniac ( I have been in Hangdian for more than a year , Even people who get lost on campus , Khan, ~), But cao'er still likes traveling very much , Because on the journey I'll meet a lot of people ( Prince charming ,^0^), A lot of things , It's also abundant ...

  9. hdu 2066 A solo trip ( Shortest path problem )

    shortest path ································· There are a lot of similar problems that won't ! Learn slowly !!!!. progress , Even a little every day ! ( Love is not a small thing , It's really the accumulation of small things !( Listen to cool dog music , very ...

Random recommendation

  1. CSS3 text-shadow

    <!DOCTYPE html > <html > <head> <meta charset="utf-8"> <title&g ...

  2. About Memcache mutex design-mode .net Realization

    I've seen it online before memcache-mutex Scene analysis and implementation code , There will be .net The way to achieve it , Of course, here is mainly based on the original pseudo code , Take this as a summary and record . If you are interested in the implementation, try the code provided in this article ...

  3. docker( 6、 ... and ) Use docker-maven-plugin Plug in build docker Mirror image ( Deprecated )

    You can refer to the blog :https://blog.csdn.net/aixiaoyang168/article/details/77453974 docker-maven-plugin The official website recommends using it in new projects do ...

  4. Functional programming - First glance F#

    A large number of books on functional programming languages will eventually be used Fuctor,Monad,Monoids, Category theory and other words scare away imperative language players , So I try to avoid these problems , Uncovering the practical results of these complex words . In addition, I will try to use C ...

  5. STM32——C Language knowledge points : The pointer 、 Structure

    /* ============================================================================ Name : Cyuyanfuxi.c ...

  6. Use AdminLTE stay content District , Open the corresponding page

    Reference resources :https://bbs.csdn.net/topics/391846671 ask : Like opening starter.html, Then click on the link in the left column ( Such as user.html) When , How to achieve... On the right cont ...

  7. Shell Script Hello World

    #!/bin/bash echo "Hello World !" “#!” It's an agreed mark , It tells the system what interpreter is needed to execute this script , That is, what kind of Shell.echo The command is used to show the window ...

  8. .net Use minimal heap to implement TopN Algorithm

    Test code : using System; using System.Collections.Generic; using System.Linq; using System.Text; namespac ...

  9. Prototype In depth exploration of

    http://www.cnblogs.com/meil/archive/2007/06/06/773645.html 1 What is? prototype JavaScript Objects in the prototype attribute , ...

  10. css There are three basic positioning mechanisms in

    css There are three basic positioning mechanisms in a. Normal document flow b. location : Relative positioning Absolute positioning Fixed position c. float 1. In the ordinary stream , Element location is determined by document order and element properties , Block level elements are arranged from top to bottom , The vertical distance between the frames is determined by the vertical distance between the frames mar ...