Buy a ticket (最短路SPFA)

2018-04-18

Buy a ticket

题意

给你n个城市，m条无向路，每条路有vi的权值（>0），每个城市有ai的音乐会花费。

某人想去看音乐会，如果她在i城，他要去j城看演出，那么要花费的钱相当于来回的路费加上j城的演唱会的钱（也可以在自家看演出）。求的是，每个城市的人看一场音乐会的最少花费。

思路

很熟悉的思路，定义一个超级原点，将超级原点和每个城市连起来，路的权值设为该城市的音乐会花费，同时加其他的路的权值设为原来的两倍（来回的花费），那么从原点到每个城市的最小花费就是每个城市的人看音乐会的最小花费。（最短路）

开头用dijkstra写，看了一下复杂度肯定会T，o(n^2)的样子，然后交了一发。后来换用SPFA，队列啥的，还是T，然后看了一下过的人的代码，发现他们用优先队列优化，将花费大的放在了前面。

看！代码

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m;
struct  node{
    int to; //目的
    long long val; //花费
};
struct  Node{
    int to;   
    long long val;
    bool operator<(const Node k)const{
        return val>k.val; 
    }
};
vector<node>Next[200005]; //路
int vis[200005]={0}; //在Q里的情况
long long dis[200005];  //距离原点的最短距离
void SPFA()
{
    memset(dis,INF,sizeof(dis)); 
    priority_queue<Node> Q; //修改成优先队列，默认路径花费大的放前面，是的
    Node temp;
    temp.to=0;temp.val=0;
    Q.push(temp);  //把原点先入队
    vis[0]=1;dis[0]=0; //原点到原点当然是0啦  
    int now,a;
    while(!Q.empty())
    {
        temp=Q.top();
        Q.pop();
        now=temp.to;
        vis[now]=0;  //出队的点vis更新
        for(int i=0;i<Next[now].size();i++)  //遍历连接的城市
        {
            a=Next[now][i].to;  
            if(dis[a]>(dis[now]+Next[now][i].val)) //如果从原点到这个城市的距离比中间接这个城市跳转要远
            {
                dis[a]=dis[now]+Next[now][i].val;
                if(vis[a]==0) //如果a不在队列里
                {
                    vis[a]=1;temp.to=a;temp.val=dis[a];
                    Q.push(temp);
                }
            }
        }
    }
}

int main()
{
    int ori,to;
    node temp;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d%lld",&ori,&to,&temp.val);
        temp.to=to;
        temp.val*=2;
        Next[ori].push_back(temp);
        temp.to=ori;
        Next[to].push_back(temp);
    }
    dis[0]=0;
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&dis[i+1]);
        temp.to=i+1;temp.val=dis[i+1];
        Next[0].push_back(temp);
    }
    SPFA();
    for(int i=1;i<=n-1;i++) printf("%lld ",dis[i]);
    printf("%lld\n",dis[n]);
    return 0;
}