hdu

hdu1873
看病排队：优先队列

#include<bits/stdc++.h>
using namespace std;
struct node{
    int id,lev;
    friend bool operator<(const node x,const node y){
        if(x.lev==y.lev) return x.id>y.id;
        return x.lev<y.lev;
    }
}temp;
int main(){
    int t,a,b;
    string s1;
    while(cin>>t){
        priority_queue<node>q[4];
        temp.id=0; 
      while(t--){
          cin>>s1;
          if(s1[0]=='I'){
              cin>>a>>b;
              temp.id++;
              temp.lev=b;
              q[a].push(temp);
          }
          else{
              cin>>a;
              if(!q[a].empty()){
                  cout<<q[a].top().id<<endl;
                  q[a].pop();
              }
              else {
                  puts("EMPTY");
              }
          }
      }
    }

}

hdu 1535 Invitation Cards
题意：n个点，求编号为1的点到所有点最短路的和加上所有点到1的最短路的总和
建两个图，一个反向

#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
const ll INF = 1e9;
const ll NUM =1000005;
struct edge{
    int to,next,w;//i就是起点，to是终点，next下一条边，w权值
}edge[NUM],edge2[NUM];
struct s_node{
    int id,n_dis;//id:结点 n_dis:结点到起点的距离
    s_node(int b,int c){
        id = b;
        n_dis = c;
    }
    bool operator<(const s_node &a)const{
        return n_dis>a.n_dis;
    }//路径小的先出队
};
int n,m,cnt,cnt1;
int head[NUM],head1[NUM];
int pre[NUM];//前驱结点
/*void print_path(int s,int t){
    if(s==t) {printf("%d",s);return ;}
    print_path(s,pre[t]);
    printf("%d",t);
}*/
void addedge(int u,int v,int w){
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}//链式前向星存图
void addedge2(int u,int v,int w){
    edge2[cnt1].to=v;
    edge2[cnt1].w=w;
    edge2[cnt1].next=head1[u];
    head1[u]=cnt1++;
}
ll dis[NUM]; //记录所有的结点到起点的距离
bool done[NUM];//done[i]=true表示到结点i的最短路径已经找到
ll dijkstra(int s){
    for(int i=1;i<=n;i++){dis[i]=INF;done[i]=false;}
    dis[s]=0;//起点到自己的距离的为0
    priority_queue<s_node>Q;//优先队列储存结点信息
    Q.push(s_node(s,dis[s]));//起点先进队
    while(!Q.empty()){
        int  u = Q.top().id;//pop出起点距离最小的结点
        Q.pop();
        if(done[u]) continue;//丢弃找到最短路径的结点，即集合A中的结点
        done[u] = true;
        for(int i=head[u];~i;i=edge[i].next){   //利用head回溯，检查结点u的所有邻居
            int y = edge[i].to,w=edge[i].w;//u.id的第i个邻居是y.to
            if(done[y]) continue; //丢弃已经找到最短路径的邻居结点
            if(dis[y]>dis[u]+w){
                dis[y] = dis[u]+w;
                Q.push(s_node(y,dis[y]));
                //扩展新的邻居结点，放到优先队列中

                //pre[y.to] = u.id;
                //如果有需要就记录路径
            }
        }
    } 
    ll sum=0;
    for(int i=1;i<=n;i++)  sum+=dis[i];
    return sum;
}
ll dijkstra1(int s){
    for(int i=1;i<=n;i++){dis[i]=INF;done[i]=false;}
    dis[s]=0;//起点到自己的距离的为0
    priority_queue<s_node>Q;//优先队列储存结点信息
    Q.push(s_node(s,dis[s]));//起点先进队
    while(!Q.empty()){
        int  u = Q.top().id;//pop出起点距离最小的结点
        Q.pop();
        if(done[u]) continue;//丢弃找到最短路径的结点，即集合A中的结点
        done[u] = true;
        for(int i=head1[u];~i;i=edge2[i].next){   //利用head回溯，检查结点u的所有邻居
            int y = edge2[i].to,w=edge2[i].w;//u.id的第i个邻居是y.to
            if(done[y]) continue; //丢弃已经找到最短路径的邻居结点
            if(dis[y]>dis[u]+w){
                dis[y] = dis[u]+w;
                Q.push(s_node(y,dis[y]));
                //扩展新的邻居结点，放到优先队列中

                //pre[y.to] = u.id;
                //如果有需要就记录路径
            }
        }
    } 
    ll sum=0;
    for(int i=1;i<=n;i++)  sum+=dis[i];
    return sum;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        memset(head,-1,sizeof(head));
        memset(head1,-1,sizeof(head1));
        cnt=cnt1=0;
        cin>>n>>m;
        for(int i = 1;i<=m;i++){
            int u,v,w;
            cin>>u>>v>>w;
            addedge(u,v,w);
            addedge2(v,u,w);
        }
        printf("%lld\n",dijkstra(1)+dijkstra1(1));

    }
}