Dijkstra最短路算法由于每次更新dis[i]的最小值（即一规定的点到点i 的最短路），再通过下一个最短更新其他点（不包括已经求出最短的点）；

such as：

#include<bits/stdc++.h>
using namespace std;const int inf = 0x7FFFFFFF;
const int N = 505;
int Map[N][N], vis[N], Dis[N];int main(void)
{int n, m, u, v, dis, st, ed, next;scanf("%d%d",&n,&m);for(int i=0; i<=n; i++){Dis[i] = inf;for(int j=0; j<=n; j++)Map[i][j] = inf;}while(m--){scanf("%d%d%d",&u,&v,&dis);Map[u][v] = min(Map[u][v],dis);Map[v][u] = Map[u][v];}scanf("%d%d",&st,&ed);Dis[st] = 0;vis[st] = 1;while(st != ed){int i;int Min = inf;for( i=0; i<=n; i++){if(Map[st][i]!=inf)Dis[i] = min(Dis[i],Map[st][i] + Dis[st]);if(!vis[i] && Dis[i] < Min){next = i;Min = Dis[i];}}if(Min == inf) break;else{st = next;vis[st] = 1;}}if(Dis[ed] == inf) puts("-1");else printf("%d\n",Dis[ed]);return 0;
}

因为板子也不难（我十分自信我会了），然后就在洛谷上栽跟头了，【洛谷p4779】最短路模板，我将我的蒻蒻板子交上去后是一片的MLE，for 一个 example：然后蒻蒻本蒻怀着不可置信地去瞅了一下题解区，然后一个新世界的大门就向我敞开了：有邻接表，前向星优化内存，有优先队列priority_queue<T> q 来优化Dijkstra的dis[i]数组更新过程。

下面就是蒻蒻本蒻的代码：

是能够完美AC：

 

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, s;
int vis[100005];
int dis[100005];
struct edge{int from, to, dis;
};
struct node{int w, dis;bool operator <(const node &x) const{return dis > x.dis;}
};
vector<edge> e[100005];void dij(){priority_queue<node> q;for(int i=1; i<=n; i++){vis[i] = 0;dis[i] = inf;}node e1;e1.w = s;e1.dis = 0;dis[s] = 0;q.push(e1);while(!q.empty()){node e2;e2 = q.top(); q.pop();int u = e2.w;if(vis[u]) continue;vis[u] = 1;for(int i=0; i<e[u].size(); i++){int v = e[u][i].to;if(dis[u]+e[u][i].dis<dis[v]){dis[v] = dis[u] + e[u][i].dis;if(!vis[v]){e2.w = v;e2.dis = dis[v];q.push(e2);}}}}
}
int main(){cin >> n >>m >>s;for(int i=0; i<m ;i++){int a, b, c;cin >> a >> b >> c;edge e1;e1.dis=c;e1.to=b;e1.from=a;e[a].push_back(e1);}dij();for(int i=1; i<=n; i++)cout << dis[i] << " ";return 0;
}