Dijkstra不能用于负权边的图

why? 目光短浅

详见：csdn

题解

1.N的大小达到1e5不能使用邻接矩阵（爆空间）,是稀疏图，要使用邻接表。
2.dist[i]存当前1到i点的最短路径,Q是优先队列存最短的路径

自创struct代码

之所以自己写了一个II是因为priority_queue默认按照pair.first进行排序
自己写的struct II重载了大于号使得按照second排序

#include<iostream>
using namespace std;
#include<algorithm>
#include<queue>
#include<cstring>
typedef struct II{
    int first,second;
    bool operator>(const II &w)const{
        return second>w.second;
    }
    II(int a,int b){
        first =a;
        second=b;
    }
}II;
const int N=1e6+10;
int n,m;
int dist[N],h[N],e[N],ne[N],w[N],idx;
bool st[N];
void add(int a,int b,int c){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    w[idx++]=c;
}
int dijkstra(int a){
   dist[a]=0;
   priority_queue<II,vector<II>,greater<II> > Q;
   Q.push(II(a,0));
   while(Q.size()){
       II t=Q.top();
       Q.pop();
       if(st[t.first]) continue;//冗余最短路径全部出队
       st[t.first]=true;
       for(int i=h[t.first];i!=-1;i=ne[i]){
           if(dist[e[i]]>t.second+w[i]){
               dist[e[i]]=t.second+w[i];
               Q.push(II(e[i],dist[e[i]]));//更新一条最短路径就加到堆里面一个
           }
       }
   }
   if(dist[n]==0x3f3f3f3f) return -1;
   return dist[n];
}
int main(void){
    int a,b,c;
    cin>>n>>m;
    memset(h,-1,sizeof(h));
    memset(dist,0x3f,sizeof(dist));
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        add(a,b,c);
    }
    cout<<dijkstra(1);

}