既然要学习算法，就要学习到它的精髓，才能够使用起来得心应手。
我还是远远不够啊。
早就知道，dijkstra 算法可以用优先队列优化，我却一直不知道该怎样优化。当时，我的思路是这样的：假设有n个顶点，将这n个顶点的id和距原点的距离放在结构体内，再将这n个结构体放入优先队列中，堆顶是距源点距离最小的点。每次要更新距离时，仅仅只需要取堆顶的数就可以了。然而，具体要怎样更新堆内各点的距离呢？将堆顶取出，更新后再放回去？这样的话堆顶永远都会是同一个元素了，因为堆顶元素在更新后，还是距离最小的。那么我们可以依次取出堆顶元素，放在结构体数组之内，等待更新完毕后再放回去，那么这样的时间复杂度是2*n,而原先的时间复杂度，也是2*n，这样的优化没有意义，反而还多了一个结构体数组浪费空间。
如果你也和我的想法一样，那我们真是太有缘分了，看来大家都是蠢的七窍流血的一类人啊，你是不是也和我一样，正在反思自己是不是应该放弃学习算法啊？实际上，在dijkstra里面，有一个十分重要的标记数组，这个标记数组决定了，已经确定了最短距离的点，就不要再次优化了！你明白了吧，想想自己真是蠢呐，竟然忘记如此重要的数组！
让我们再次思考，是否要将所有没有确定的点全部放入数组呢？
当然不要，我们只要将刚刚更新过的放进去就行，因为那些没有更新的，肯定不会是路径最短的。那么我们每次都放，就会导致某个节点被放进去很多次了，但是没关系，他们的被放进去的时候，距离是不同的，所以距离大的会沉到底下去，最短路径一定不是他们（对同一节点来说），他们要出推时，我们只处理第一个，以后的一律不处理。这个我们还用一个标记数组来解决。
代码自己去找吧，https://blog.csdn.net/jobsandczj/article/details/49962557，这个人写得不错，除了码风很丑，加上竟然使用邻接矩阵。。。然后还有book数组定义了没有使用以外，其他的都还行。
如果你连这些问题都不想面对，或者根本就不想看代码的话，你还是转行吧。
在此还是贴上自己的模板吧
这个模板跑起来反而比我原先的代码更慢，我觉得这是邻接表的问题，因为在一开始我用的是啊哈算法的邻接表，而现在用的是vector，再加上可能我在做的那个题太水了，数据量太小，导致优先队列的优势没有发挥出来。
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct node
{
int x;
int s; bool operator<(const node p)const
{
return p.s<s;
}
};
bool book[100];
int dis[100];
const int inf = 2100000000;
int main()
{
vector<int>u[100];
vector<int>w[100];
int n,m;
cin>>n>>m;
int x,y,z;
for(int i=0;i<m;i++){
cin>>x>>y>>z;
u[x].push_back(y);
w[x].push_back(z);
}
fill(dis,dis+n+1,inf);
dis[1]=0;
priority_queue<node>q;
node exa;
exa.x=1;
exa.s=0;
q.push(exa);
while(!q.empty()){
exa=q.top();q.pop();
if(book[exa.x]){continue;}
book[exa.x]=true;
int t=exa.x;
for(int i=0;i<u[t].size();i++){
if(dis[u[t][i]]>dis[t]+w[t][i]){
dis[u[t][i]]=dis[t]+w[t][i];
exa.s=dis[u[t][i]];
exa.x=u[t][i];
q.push(exa);
}
}
}
for(int i=1;i<=n;i++){
cout<<dis[i]<<" ";
}
cout<<endl;
}
下面的代码包括了对路径的输出，只是我没有找到这样的题，所以不敢保证算法的正确性：
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
struct node
{
int x;
int s; bool operator<(const node p)const
{
return p.s<s;
}
};
bool book[100];
int dis[100];
int f[1000];
const int inf = 2100000000;
int main()
{
vector<int>u[100];
vector<int>w[100];
int n,m;
cin>>n>>m;
int x,y,z;
for(int i=0;i<m;i++){
cin>>x>>y>>z;
u[x].push_back(y);
w[x].push_back(z);
}
fill(dis,dis+n+1,inf);
fill(f,f+n+1,-1);
dis[1]=0;
priority_queue<node>q;
node exa;
exa.x=1;
exa.s=0;
q.push(exa);
while(!q.empty()){
exa=q.top();q.pop();
if(book[exa.x]){continue;}
book[exa.x]=true;
int t=exa.x;
for(int i=0;i<u[t].size();i++){
if(dis[u[t][i]]>dis[t]+w[t][i]){
dis[u[t][i]]=dis[t]+w[t][i];
exa.s=dis[u[t][i]];
f[u[t][i]]=t;
exa.x=u[t][i];
q.push(exa);
}
}
}
stack<int>h;
for(int i=1;i<=n;i++){
cout<<dis[i]<<": ";
int ah=f[i]; while(ah!=-1){
h.push(ah);
ah=f[ah];
}
while(!h.empty()){
cout<<h.top()<<" ";
h.pop();
}cout<<i<<" ";
cout<<endl;
}
cout<<endl;
}
每个人都是被动出生，只有选择死亡才是真正的*！