CCPC-WannaflyWinterCampDay1Div1-爬爬爬山-[最短路][堆优化dijkstra]

#include
using namespace std;
typedef long long ll;
typedef pairint> P; //first是最短距离，second是节点编号
#define mk(x,y) make_pair(x,y)

const int maxn=1e5+10;
const ll INF=1e17;

int n,m,k;
ll h[maxn];

struct Edge{
    int u,v;
    ll w;
};
vector E;
vector<int> G[maxn];
void addedge(int u,int v,ll w)
{
    E.push_back((Edge){u,v,w});
    G[u].push_back(E.size()-1);
}

ll dist[maxn];
bool vis[maxn];
priority_queue, greater
 > Q;
void dijkstra(int s,int t)
{
    for(int i=1;i<=n;i++) dist[i]=INF, vis[i]=0;
    dist[s]=0, Q.push(mk(0,s));
    while(!Q.empty())
    {
        int u=Q.top().second; Q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto x:G[u])
        {
            Edge &e=E[x]; int v=e.v;
            if(vis[v]) continue;
            if(dist[v]>dist[u]+e.w) dist[v]=dist[u]+e.w, Q.push(mk(dist[v],v));
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
    for(int i=1;i<=m;i++)
    {
        int u,v; ll w,o;
        scanf("%d%d%lld",&u,&v,&w);
        o=0; if(h[1]+k1]-k)*(h[v]-h[1]-k);
        addedge(u,v,w+o);
        o=0; if(h[1]+k1]-k)*(h[u]-h[1]-k);
        addedge(v,u,w+o);
    }
    dijkstra(1,n);
    cout<endl;
}