P1807题解。。。

xiaolou · 2018-10-02 15:58:23 · 题解

关于这道题。。。其实就是一道dijkstra模板改改吧。。。（我直接复制了板子改了几行就A了）

//code

#include <bits/stdc++.h>
using namespace std;
#define MAXN 10005
#define MAXM 500005
int n,m,s,u,v,c,tot,dis[MAXN];//从1到每个点的距离，刚开始脑残了，以为每个点都要求。。。
bool vis[MAXN];//表示每个点有没有被访问过。。。
struct Node//结构体存边
{
    int v,c;
    Node *next;
}*h[MAXN],pool[MAXM];
struct Queue
{
    int id,dis;
    bool operator<(const Queue t) const
    {
        return dis<t.dis;
    }
};
priority_queue <Queue> q;//队列
Queue tmp;
void ae(int u,int v,int c)//addedge，邻接表存边（本人只会写指针。。。）
{
    Node *p=&pool[tot++];
    p->v=v;p->c=c;p->next=h[u];h[u]=p;
}
void dijkstra()
{
    for(int i=1;i<=n;i++) 
        dis[i]=0;
    dis[s]=0;
    tmp.id=s;tmp.dis=0;q.push(tmp);
    while(!q.empty())
    {
        tmp=q.top();q.pop();
        int u=tmp.id;
        for(Node *j=h[u];j;j=j->next)
        {
            if(!vis[j->v]&&dis[j->v]<dis[u]+ j->c)
            {
                dis[j->v]=dis[u]+j->c;
                tmp.id=j->v;tmp.dis=dis[j->v];q.push(tmp);
            }
        }
    }
}//dijkstra的板子
int main()
{
    cin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        cin >> u >> v >> c;
        ae(u,v,c);
    }
    s=1;
    dijkstra();
    if(!dis[n])
        cout << "-1";//注意，千万不要把“-1”打成‘-1’，本蒟蒻被坑了30分钟
    else
        cout << dis[n];
    return 0;//2333
}