关于dij算法的理解..

因为本人很弱没学过dp,试图用dp写最短路,结果算法写出来复杂度应该大概有n^2,本人对算法复杂度又不是很敏感.所以就炸了,呜呜呜

void dfs1(ll x)
{
    vis1[x]=1;
   // cout<<1<<endl;
    for(ll i=0;i<v1[x].size();i++)
    {
        ll so=v1[x][i].son;
        if(vis1[so]) continue;
        ll va=v1[x][i].val;
        dp1[so]=min(dp1[so],dp1[x]+va);
        if(dp1[so]!=inf) continue;
        dfs1(so);
    }
    vis1[x]=0;
}

下面介绍dij,什么是dij呢?怎么从根节点跑出到每个地方的最短路呢?其实类似于bfs..思路也十分简单..我们从根节点开始进行bfs,每次bfs都选择最小的并记录答案进行下次bfs.仔细想一想,这个算法是否正确呢?答案是毋庸置疑的..因为你现在已经有了一定的路线进行选择了.下次走一定要比现在大,因为权值是正数的.下面代码中讲讲dij是如何实现的..
首先考虑每次选取最小的,我们考虑用一个优先队列来维护..并且我们也可以不用思考的直接把边的权值推进去就好了,用个vis数组表示这个点有没有已经确认过.假如没有确认过,就选择队列里这个点权值最小的进行bfs..代码思路就是这样,时间复杂度,大概就是（n*logn）的样子..
下面就是代码实现..

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
typedef long long ll;
const ll inf=132913423200339;
const ll mod=998244353676776;
const ll N=2e5+5;
const ll M=10+5;
const double eps=1e-7;
using namespace std;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);    }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x)          { return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
ll A(ll n,ll m,ll mod){ll sum=1; for(int i=n;i>=n-m+1;i--) sum=(sum*i)%mod; return sum%mod;}
ll lowbit(ll x) {return x&(-x);}
ll c[N],sum1[N],sum2[N],b[N],lsh[N],n,m,fa[13],a[N];
void add1(ll i,ll k){ while(i<=n) {c[i]+=k;i+=lowbit(i);}}//预处理ai单点修改 区间查询***预处理a[i]-a[i-1]区间修改单点查询
ll  Sum1(ll i) {ll res=0; while(i>0) res+=c[i],i-=lowbit(i);return res;}//预处理ai单点修改 区间查询***预处理a[i]-a[i-1]区间修改单点查询
void add2(ll i,ll k){ ll x=i;while(i<=n) {sum1[i]+=k;sum2[i]+=k*(x-1);i+=lowbit(i);}}//区间修改,区间查询
ll  Sum2(ll i) {ll res=0,x=i;while(i>0){ res+= x * sum1[i]-sum2[i]; i -= lowbit(i);}return res;}//区间修改,区间查询
void ls(){ll cnt; for(ll i=1;i<=n;i++) lsh[i]=a[i]; sort(lsh+1,lsh+n+1);cnt = unique(lsh+1,lsh+n+1)-lsh-1; for(int i=1;i<=n;i++)a[i]=lower_bound(lsh+1,lsh+cnt+1,a[i])-lsh;}
ll lca(ll x) { if(x==fa[x]) return x;else return fa[x]=lca(fa[x]); }//找祖先.
ll cnt1[N],cnt2[N],cnt3[N],dis1[N],dis2[N],vis1[N],vis2[N];
struct dd{
    ll id,val;
    bool operator<(const dd &d)const
    {
       return val>d.val;
    }
};
vector<dd>v1[N];
vector<dd>v2[N];
void dij1(ll x)
{
   priority_queue<dd>q;
   q.push(dd{x,0});//把起点存进去..
   while(q.size())
   {
       dd temp=q.top(); q.pop();
       if(vis1[temp.id]) continue; vis1[temp.id]=1;
       dis1[temp.id]=temp.val;
       for(ll i=0;i<v1[temp.id].size();i++)
       {
           ll son=v1[temp.id][i].id;ll va=v1[temp.id][i].val;
           if(!vis1[son])  q.push(dd{son,temp.val+va});
       }
   }
}
void dij2(ll x)
{
   priority_queue<dd>q;
   q.push(dd{x,0});//把起点存进去..
   while(q.size())
   {
       dd temp=q.top(); q.pop();
       if(vis2[temp.id]) continue; vis2[temp.id]=1;
       dis2[temp.id]=temp.val;
       for(ll i=0;i<v2[temp.id].size();i++)
       {
           ll son=v2[temp.id][i].id;ll va=v2[temp.id][i].val;
           if(!vis2[son])  q.push(dd{son,temp.val+va});
       }
   }
}
int main()
{
    ios;
    cin>>n>>m;//n个点,m条路.
    memset(dis1,inf,sizeof(dis1));
    memset(dis2,inf,sizeof(dis2));
    for(ll i=1;i<=m;i++)
    {
        cin>>cnt1[i]>>cnt2[i]>>cnt3[i];
        v1[cnt1[i]].push_back(dd{cnt2[i],cnt3[i]});//计算它到1的最短路
        v2[cnt2[i]].push_back(dd{cnt1[i],cnt3[i]});//计算它到n的最短路
    }
    dij1(1); dij2(n);
    ll t;
    cin>>t;
    while(t--)
    {
       ll x;   cin>>x;
       if(dis1[cnt2[x]]+dis2[cnt1[x]]+cnt3[x]<dis1[n]) cout<<"YES"<<endl;
       else                                            cout<<"NO"<<endl;
    }
    return 0;
}