1007 公交线路 dijkstra板子+总结

标签：dist int 队列 dijkstra 复制 公交线路 1007

 链接：https://ac.nowcoder.com/acm/contest/26077/1007
来源：牛客网

题目描述

P市有n个公交站，之间连接着m条道路。P市计划新开设一条公交线路，该线路从城市的东站（s点）修建到西站（t点），请为P市设计一条满足上述条件并且最短的公交线路图。

输入描述:

第一行有4个正整数n，m，s，t。

接下来m行，每行3个数a,b,v描述一条无向道路a——b，长度为v。

输出描述:

如果有解，输出一行，表示满足条件的最短公交线路的长度c。

否则，输出“-1”

示例1

输入

复制 3 3 1 2 1 2 3 2 3 4 1 3 5

3 3 1 2
1 2 3
2 3 4
1 3 5

输出

复制 3

3

示例2

输入

复制 3 3 1 2 1 2 5 2 3 3 1 3 1

3 3 1 2
1 2 5
2 3 3
1 3 1

输出

复制 4

4

示例3

输入

复制 3 1 1 1 1 2 1

3 1 1 1
1 2 1

输出

复制 0

0

备注:

对于100%的测试数据：
1 ≤ s,t ≤ n ≤ 1000
1 ≤ m ≤ 10000
1 ≤ 道路的长度 ≤ 10000

分析

最短路dijkstra队列优化板子，求出s 点到 t 点的最短路长度。

优先队列以距离排序，省去dijkstra第一个找出最小值步骤

因为先前放入优先队列的元素不能修改也不能删除，所以优先队列总共有m个元素，取出放入m次，复杂度有：mlogm

m=1e5。总复杂度也就1e7左右

 

ps：普通dijkstra是n^2，由于两层的n次遍历是要暴力算的，另外有m次松弛操作（有时候直接忽略已经被删除的边，写n次松弛操作）

普通dijkstra：复杂度是o(n^2+m)，在稠密图中常用（点多（最多也就5000个点左右），边少）

优先队列优化：mlogm适合边多点少，m最多也就1e7吧。

//-------------------------代码----------------------------

//#define int ll
const int N = 1e5+10;
int n,m,idx,e[N],ne[N],w[N],h[N<<1];
void add(int a,int b,int c) {
    e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx ++ ;
}
int dist[N];
bool vis[N];
int st,ed;
void dij() {
    ms(dist,0x3f);
    priority_queue<pii,V<pii>,greater<pii>> q;
    q.push({0,st});
    dist[st] = 0;
    while(q.size()) {
        auto mm = q.top();
        q.pop();
        int t = mm.y;
        if(vis[t]) continue;
        vis[t] = 1;
        if(t == ed) {
            break;
        }
        for(int i = h[t];~i;i=ne[i]) {
            int j = e[i];
            if(dist[j] > dist[t] + w[i]) {
                dist[j] = dist[t] + w[i];
                q.push({dist[j],j});
            }
        }
    }
    if(dist[ed] == 0x3f3f3f3f) {None;}
    else cout<<dist[ed]<<endl;
}

void solve()
{
    ms(h,-1);
    cin>>n>>m>>st>>ed;
    fo(i,1,m) {
        int a,b,v;cin>>a>>b>>v;
        add(a,b,v);add(b,a,v);
    }
    dij();
}
void main_init() {}
signed main(){
    AC();clapping();TLE;
    cout<<fixed<<setprecision(12);
    main_init();
//  while(cin>>n,n)
//  while(cin>>n>>m,n,m)
//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

 

标签：dist,int,队列,dijkstra,复制,公交线路,1007
From： https://www.cnblogs.com/er007/p/16586729.html