2017年3月 .NET技术大版内专家分月排行榜第三2017年2月 .NET技术大版内专家分月排行榜第三2016年9月 .NET技术大版内专家分月排行榜第三2016年8月 .NET技术大版内专家分月排行榜第三2016年7月 .NET技术大版内专家分月排行榜第三2016年3月 .NET技术大版内专家分月排行榜第三2016年1月 .NET技术大版内专家分月排行榜第三2015年12月 .NET技术大版内专家分月排行榜第三2015年11月 .NET技术大版内专家分月排行榜第三
2013年5月 总版技术专家分月排行榜第一
2016年7月 总版技术专家分月排行榜第二2016年3月 总版技术专家分月排行榜第二2015年12月 总版技术专家分月排行榜第二2014年8月 总版技术专家分月排行榜第二2014年7月 总版技术专家分月排行榜第二2013年6月 总版技术专家分月排行榜第二
2013年5月 总版技术专家分月排行榜第一
2016年7月 总版技术专家分月排行榜第二2016年3月 总版技术专家分月排行榜第二2015年12月 总版技术专家分月排行榜第二2014年8月 总版技术专家分月排行榜第二2014年7月 总版技术专家分月排行榜第二2013年6月 总版技术专家分月排行榜第二
2017年2月 总版技术专家分月排行榜第三
2017年5月 .NET技术大版内专家分月排行榜第一2017年4月 .NET技术大版内专家分月排行榜第一2017年3月 .NET技术大版内专家分月排行榜第一2017年2月 .NET技术大版内专家分月排行榜第一2016年10月 .NET技术大版内专家分月排行榜第一2016年8月 .NET技术大版内专家分月排行榜第一2016年7月 .NET技术大版内专家分月排行榜第一
2017年2月 总版技术专家分月排行榜第三
2017年5月 .NET技术大版内专家分月排行榜第一2017年4月 .NET技术大版内专家分月排行榜第一2017年3月 .NET技术大版内专家分月排行榜第一2017年2月 .NET技术大版内专家分月排行榜第一2016年10月 .NET技术大版内专家分月排行榜第一2016年8月 .NET技术大版内专家分月排行榜第一2016年7月 .NET技术大版内专家分月排行榜第一
2017年2月 总版技术专家分月排行榜第三
2017年5月 .NET技术大版内专家分月排行榜第一2017年4月 .NET技术大版内专家分月排行榜第一2017年3月 .NET技术大版内专家分月排行榜第一2017年2月 .NET技术大版内专家分月排行榜第一2016年10月 .NET技术大版内专家分月排行榜第一2016年8月 .NET技术大版内专家分月排行榜第一2016年7月 .NET技术大版内专家分月排行榜第一
匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。更多期待，更多热爱
一个人的旅行
Time Limit:
MS (Java/Others)&&&&Memory Limit:
K (Java/Others)Total Submission(s): 36107&&&&Accepted Submission(s): 12313
Problem Description
虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中 会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。
输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=&(a,b)&=1000;a,b 之间可能有多条路)接着的第T+1行有S个数，表示和草儿家相连的城市；接着的第T+2行有D个数，表示草儿想去地方。
输出草儿能去某个喜欢的城市的最短时间。
Sample Input
Sample Output
给你一些通路，告诉你通过这些通路所需的时间。
给你一些起点，一些终点。
求从任意一起点，到任意一终点，所需的最短时间
分析：多起点多终点最短路径问题
多次使用经典dijkstra单源最短路径算法（求一起点，到其他所有点的最短路径,找所有终点中最小花费。依次操作完每个起点。。。）
#include&stdio.h&
#include&string.h&
#define inf 0x3f3f3f3f
int map1[<span style="color: #02][<span style="color: #02],dis[<span style="color: #02],visit[<span style="color: #02];///map1[][]存储所有边，
///dis[]存储第一个点到第i个点的路径长度，visit[]存储各点的访问状态
int start[<span style="color: #02],end1[<span style="color: #02];
const int n=<span style="color: #02;
void dijstra(int s1)
int i,j,pos=<span style="color: #,min1;
memset(visit,<span style="color: #,sizeof(visit));
for(i=<span style="color: #;i&=n;++i)
dis[i]=map1[s1][i];///第一个点到其他所有点的距离
visit[s1]=<span style="color: #;
dis[s1]=<span style="color: #;
for(i=<span style="color: #;i&n;i++)///剩余n-1个点，广度优先，依次求取距离原点的 最短路径长度
for(j=<span style="color: #;j&=n;++j)
if(!visit[j]&&min1&dis[j])
min1=dis[j];
}///找到最小dis值
visit[pos]=<span style="color: #;
for(j=<span style="color: #;j&=n;++j)
if(!visit[j]&&dis[j]&dis[pos]+map1[pos][j])///<span style="color: #-&j的距离是否可通过i-&pos-&j距离更短？
dis[j]=dis[pos]+map1[pos][j];
int main()
int t,s,d;
while(~scanf("%d%d%d",&t,&s,&d)&&t)
for(i=<span style="color: #;i&=<span style="color: #02;++i)
for(j=<span style="color: #;j&=<span style="color: #02;++j)
map1[i][j]=
int a,b,c;
for(i=<span style="color: #;i&=t;++i)///输入两点+权值
scanf("%d%d%d",&a,&b,&c);
if(c&map1[a][b])
map1[a][b]=map1[b][a]=c;///无向边
for(int i=<span style="color: #;i&s;i++)
scanf("%d",&start[i]);
for(int i=<span style="color: #;i&d;i++)
scanf("%d",&end1[i]);
for(int i=<span style="color: #;i&s;i++)
dijstra(start[i]);///对每个起点使用
for(int j=<span style="color: #;j&d;j++)///求到多个目的地的距离中的最小
cnt=cnt&dis[end1[j]]?dis[end1[j]]:
printf("%d\n",cnt);
return <span style="color: #;
网搜其他解法，抽时间理解学习，加注释。
法二：SPFA， 将起点都推入队列。求出各个终点的最短时间。然后再找到最短的；
///SPFA shortest path faster algorithm
#include &cstdio&
#include &vector&
#include &algorithm&
#include &queue&
#define INF 0xfffffff
const int maxn = <span style="color: #10;
using namespace
struct node{
node(int v=<span style="color: #,int len=<span style="color: #):v(v),len(len){}
int st[<span style="color: #10];
int goal[<span style="color: #10];
vector&node&G[maxn];
int minDist[maxn];
int inqueue[maxn];
int T,S,D;
void init(){
for(int i=<span style="color: #;i&i++){
minDist[i]=INF;
inqueue[i]=<span style="color: #;
G[i].clear();
int Dijkstra(){
queue&int &Q;
for(int i=<span style="color: #;i&S;i++){ ///将所有的起点 都推入队列
inqueue[st[i]]=true;
minDist[st[i]]=<span style="color: #;
Q.push(st[i]);
while(!Q.empty()){
int vex = Q.front();
inqueue[vex]=<span style="color: #;
for(int i=<span style="color: #;i&G[vex].size();i++){
int v = G[vex][i].v;
if(G[vex][i].len+minDist[vex]&minDist[v]){ ///松弛操作，找到最短边
minDist[v]=G[vex][i].len+minDist[vex];
if(!inqueue[v])
inqueue[v]=<span style="color: #;
Q.push(v);
int Min = INF;
for(int i=<span style="color: #;i&D;i++){ ///在终点找到用时最小的终点
Min = min(minDist[goal[i]],Min);
printf("%d\n",Min);
int main(){
while(scanf("%d%d%d",&T,&S,&D)!=EOF){
for(int i=<span style="color: #;i&T;i++){
scanf("%d%d%d",&a,&b,&len);
G[a].push_back(node(b,len));
G[b].push_back(node(a,len));
for(int i=<span style="color: #;i&S;i++){
scanf("%d",&st[i]);
for(int i=<span style="color: #;i&D;i++){
scanf("%d",&goal[i]);
Dijkstra();
return <span style="color: #;
#include &cstdio&
#include &cstring&
#include &queue&
#include &vector&
#include &algorithm&
using namespace
int t, s, d,
int dis[<span style="color: #10];
bool vis[<span style="color: #10];
int goal[<span style="color: #10];
struct edge
}e[<span style="color: #10];
int head[<span style="color: #10];
queue &int&
void adde(int u, int v, int w)
e[k].next = head[u];
head[u] = k++;
void input()
for (int i = <span style="color: #; i &= i++)
scanf("%d%d%d", &u, &v, &w);
adde(u, v, w);
adde(v, u, w);
for (int i = <span style="color: #; i & i++)
scanf("%d", &v);
adde(<span style="color: #, v, <span style="color: #);
adde(v, <span style="color: #, <span style="color: #);
for (int i = <span style="color: #; i & i++)
scanf("%d", &goal[i]);
void init()
k = <span style="color: #;
memset(head, -<span style="color: #, sizeof(head));
memset(dis, <span style="color: #x3f, sizeof(dis));
memset(vis, <span style="color: #, sizeof(vis));
dis[<span style="color: #] = <span style="color: #;
while (!q.empty())
void spfa()
q.push(<span style="color: #);
vis[<span style="color: #] = <span style="color: #;
while (!q.empty())
int u = q.front();
vis[u] = <span style="color: #;
for (int i = head[u]; i != -<span style="color: #; i = e[i].next)
int v = e[i].v;
if (dis[v] & dis[u] + e[i].w)
dis[v] = dis[u] + e[i].w;
if (!vis[v])
vis[v] = <span style="color: #;
q.push(v);
void solve()
int ans = <span style="color: #x3f3f3f3f;
for (int i = <span style="color: #; i & i++)
ans = min(ans, dis[goal[i]]);
printf("%d\n", ans);
int main()
while (scanf("%d%d%d", &t, &s, &d) == <span style="color: #)
return <span style="color: #;
【Floyd-Warshall算法】
效率是O（n^3） 用到了DP的思想
#include &cstdio&
#include &vector&
#include &queue&
#define INF 0xfffff
const int maxn = <span style="color: #10;
using namespace
int map[maxn][maxn];
int st[maxn];
int goal[maxn];
void init(){
for(int i=<span style="color: #;i&i++){
for(int j=<span style="color: #;j&j++){
if(i==j) map[i][j]=<span style="color: #;
map[i][j]=INF;
int main(){
int T,S,D;
while(scanf("%d%d%d",&T,&S,&D)!=EOF){
int Min=INF,Max=-<span style="color: #;
for(int i=<span style="color: #;i&T;i++){
scanf("%d%d%d",&a,&b,&len);
if(a&Max) Max =
if(b&Max) Max =
if(b&Min) Min =
if(a&Min) Min =a;
if(len&map[a][b])
map[a][b]=map[b][a]=
for(int k=Mk&=Mk++){
for(int i=Mi&=Mi++){
if(map[i][k]!=INF) ///没有这句优化就超时了
for(int j=Mj&=Mj++){
if(map[i][j]&map[i][k]+map[k][j])
map[i][j]=map[i][k]+map[k][j];
for(int i=<span style="color: #;i&S;i++)
scanf("%d",&st[i]);
for(int i=<span style="color: #;i&D;i++)
scanf("%d",&goal[i]);
int ans=INF;
for(int i=<span style="color: #;i&S;i++){
for(int j=<span style="color: #;j&D;j++){
if(map[st[i]][goal[j]]&ans)
ans=map[st[i]][goal[j]];
printf("%d/n",ans);
return <span style="color: #;
阅读(...) 评论()我的简书：http://jianshu.io/users/sbLy2t/ 文章是人的魂器，想了解我...
LostAbaddon的最新日记
&&&&&&&&&&&&
&(1人喜欢)
&&&&&&&&&&&&
如果时光倒流…… · 57870人浏览
124519人浏览
236125人浏览
126253人浏览
962969人浏览
58092人浏览