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[2005][2005];
- int n,m;
- int dis[2005];
- bool used[2005];
- int main(){
- memset(g,0x3f,sizeof(g));
- cin>>n>>m;
- for(int i=1;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[1]=0;
- for(int i=1;i<=n;++i){
- int minn=0x3f3f3f3f,minn_j=0;
- for(int j=1;j<=n;++j){
- if(used[j]==false&&dis[j]<minn){
- minn=dis[j];
- minn_j=j;
- }
- }
- if(minn_j==0)
- break;
- used[minn_j]=true;
- for(int j=1;j<=n;j++)
- if(used[j]==false)
- dis[j]=min(dis[j],dis[minn_j]+g[minn_j][j]);
- }
- if(dis[n]==0x3f3f3f3f)
- cout<<-1;
- else
- cout<<dis[n];
- }
+ 领接表:
- #include<bits/stdc++.h>
- using namespace std;
- struct node{
- int to,val;
- };
- vector<node> edge[2005];
- int dis[2005];
- bool used[2005];
- int main(){
- int n,m;
- cin>>n>>m;
- int a,b,c;
- for(int i=1;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[1]=0;
- for(int i=1;i<=n;i++){
- int minn=0x3f3f3f3f,minn_j=0;
- for(int j=1;j<=n;j++){
- if(used[j]==false&&dis[j]<minn){
- minn=dis[j];
- minn_j=j;
- }
- }
- if(minn_j==0)
- break;
- used[minn_j]=true;
- int from=minn_j;
- for(int j=0;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<<-1;
- else
- cout<<dis[n];
- return 0;
- }
+ 链式前向星:
- #include<bits/stdc++.h>
- using namespace std;
- struct node
- {
- int to,val,next;
- };
- node edge[20005];
- int dis[2005];
- bool used[2005];
- int head[2005];
- int num=0;
- 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=1;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[1]=0;
- for(int i=1;i<=n;i++)
- {
- int minn=0x3f3f3f3f,minn_j=0;
- for(int j=1;j<=n;j++)
- {
- if(used[j]==false && dis[j]<minn)
- {
- minn=dis[j];
- minn_j=j;
- }
- }
- if(minn_j==0)
- break;
- used[minn_j]=true;
- int from=minn_j;
- for(int j=head[from];j!=0;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<<-1;
- else
- cout<<dis[n];
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3086315.html