1381:城市路(Dijkstra)
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 4066 通过数: 1163
【题目描述】
罗老师被邀请参加一个舞会,是在城市n,而罗老师当前所处的城市为1,附近还有很多城市2~n-1,有些城市之间没有直接相连的路,有些城市之间有直接相连的路,这些路都是双向的,当然也可能有多条。
现在给出直接相邻城市的路长度,罗老师想知道从城市1到城市n,最短多少距离。
【输入】
输入n, m,表示n个城市和m条路;
接下来m行,每行a b c, 表示城市a与城市b有长度为c的路。
【输出】
输出1到n的最短路。如果1到达不了n,就输出-1。
【输入样例】
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
【输出样例】
90
【提示】
【数据规模和约定】
1≤n≤2000
1≤m≤10000
0≤c≤10000
【来源】
No
Floyd:(被省略了。。。。)
Dijkstra:
#include<bits/stdc++.h>
using namespace std;
int g[][];
int n,m;
int dis[];
bool used[];
int main(){
memset(g,0x3f,sizeof(g));
cin>>n>>m;
for(int i=;i<=m;++i){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b]=min(g[a][b],c);
g[b][a]=min(g[b][a],c);
}
memset(dis,0x3f,sizeof(dis));
dis[]=;
for(int i=;i<=n;++i){
int minn=0x3f3f3f3f,minn_j=;
for(int j=;j<=n;++j){
if(used[j]==false&&dis[j]<minn){
minn=dis[j];
minn_j=j;
}
}
if(minn_j==)
break;
used[minn_j]=true;
for(int j=;j<=n;j++)
if(used[j]==false)
dis[j]=min(dis[j],dis[minn_j]+g[minn_j][j]);
}
if(dis[n]==0x3f3f3f3f)
cout<<-;
else
cout<<dis[n];
}
+领接表:
#include<bits/stdc++.h>
using namespace std;
struct node{
int to,val;
};
vector<node> edge[]; int dis[];
bool used[];
int main(){
int n,m;
cin>>n>>m;
int a,b,c;
for(int i=;i<=m;i++){
cin>>a>>b>>c;
node t;
t.to=b;t.val=c;
edge[a].push_back(t);
t.to=a;t.val=c;
edge[b].push_back(t);
}
memset(dis,0x3f,sizeof(dis));
dis[]=;
for(int i=;i<=n;i++){
int minn=0x3f3f3f3f,minn_j=;
for(int j=;j<=n;j++){
if(used[j]==false&&dis[j]<minn){
minn=dis[j];
minn_j=j;
}
}
if(minn_j==)
break;
used[minn_j]=true;
int from=minn_j;
for(int j=;j<edge[from].size();j++){
int to=edge[from][j].to;
int val=edge[from][j].val;
dis[to]=min(dis[to],dis[from]+val);
} } if(dis[n]==0x3f3f3f3f)
cout<<-;
else
cout<<dis[n]; return ;
}
#include<bits/stdc++.h>
using namespace std;
struct node
{
int to,val,next;
};
node edge[]; int dis[];
bool used[];
int head[];
int num=;
void add_edge(int from,int to,int val)
{
num++;
edge[num].to=to;
edge[num].val=val;
edge[num].next=head[from];
head[from]=num;
} int main()
{
int n,m;
cin>>n>>m;
int a,b,c;
for(int i=;i<=m;i++)
{
cin>>a>>b>>c;
add_edge(a,b,c);
add_edge(b,a,c);
} memset(dis,0x3f,sizeof(dis));
memset(used,false,sizeof(used));
dis[]=;
for(int i=;i<=n;i++)
{
int minn=0x3f3f3f3f,minn_j=;
for(int j=;j<=n;j++)
{
if(used[j]==false && dis[j]<minn)
{
minn=dis[j];
minn_j=j;
}
}
if(minn_j==)
break;
used[minn_j]=true;
int from=minn_j;
for(int j=head[from];j!=;j=edge[j].next)
{
int to=edge[j].to;
int val=edge[j].val;
dis[to]=min(dis[to],dis[from]+val);
}
} if(dis[n]==0x3f3f3f3f)
cout<<-;
else
cout<<dis[n]; return ;
}