2018-03-19

L2-002. 链表去重
有时候 一直写不出来就重新写一遍吧。

#include<bits/stdc++.h>
using namespace std;
struct Node{
int x;
int next;
}node[100005];
bool vis[100005];
bool v2[100005];
int q1[100005];
int q2[100005];
int main()
{

    int start,n;
    cin>>start>>n;
    memset(vis,0,sizeof(vis));
    memset(v2,0,sizeof(v2));
    for(int i=0;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        node[a].x=b;node[a].next=c;
    }

    int y=start;
    int cn=0;
    int c1,c2;c1=c2=0;
    while(y!=-1){
        if(vis[abs(node[y].x)]==0){
            cn++;
            vis[abs(node[y].x)]=1;
            v2[y]=1;
            q1[c1++]=y;
        }else{
        q2[c2++]=y;
        }
        y=node[y].next;
    }
    printf("%05d %d ",q1[0],node[q1[0]].x);
    for(int i=1;i<c1;i++){
    printf("%05d\n%05d %d ",q1[i],q1[i],node[q1[i]].x);
    }
printf("-1\n");
if(c2>0){

    printf("%05d %d ",q2[0],node[q2[0]].x);
    for(int i=1;i<c2;i++){
    printf("%05d\n%05d %d ",q2[i],q2[i],node[q2[i]].x);
    }
printf("-1\n");
}


    return 0;
}
/*
00000 2
00000 1 00002
00002 1 -1

00000 3
00000 1 00002
00002 2 00003
00003 1 -1
*/

L2-001. 紧急救援

我这道题败在 细节，还是 TM 的这个图是一个 无向图？？！！！

#include<bits/stdc++.h>
using namespace std;
#define N 505
#define INF 0x3f3f3f3f
int n,m,s,d;
int dis[N];
int num[N];
int ma[N][N];
int pre[N];
int sumnum[N];
bool vis[N];
int l[N];
void dij(){

vis[s]=1;
sumnum[s]=num[s];
dis[s]=0;
    int k=s;
    int mi=INF;

for(int i=0;i<n-1;i++){


     mi=INF;
    for(int j=0;j<n;j++){
        if(!vis[j]){
            if(dis[j]<mi){
                mi=dis[j];
                k=j;
            }
        }
    }
     vis[k]=1;
     for(int j=0;j<n;j++){
        if(!vis[j]){
            if(dis[j]>dis[k]+ma[k][j]){
                dis[j]=dis[k]+ma[k][j];
                pre[j]=k;
                sumnum[j]=sumnum[k]+num[j];
                l[j]=l[k];
            }else if (dis[j]==dis[k]+ma[k][j]){

                l[j]=l[j]+l[k];
                if(sumnum[j]<sumnum[k]+num[j]){
               pre[j]=k;
                     sumnum[j]=sumnum[k]+num[j];
                }
            }
        }
    }

}
}
int p[N];
int cn=0;
void print(int x){
if(x==-1)
    return;
    print(pre[x]);
    p[cn++]=x;
}
int main()
{
    memset(dis,0x3f,sizeof(dis));
    memset(ma,0x3f,sizeof(ma));
    memset(pre,-1,sizeof(pre));
    memset(vis,0,sizeof(vis));

    cin>>n>>m>>s>>d;
    for(int i=0;i<n;i++){
        l[i]=1;
    }
    for(int i=0;i<n;i++)ma[i][i]=0;
    for(int i=0;i<n;i++){cin>>num[i];sumnum[i]=num[i];}
    for(int i=0;i<m;i++)
      {
          int a,b,c;
          cin>>a>>b>>c;
          ma[a][b]=min(ma[a][b],c);
          ma[b][a]=ma[a][b];
          if(a==s){
            dis[b]=min(c,dis[b]);
            sumnum[b]=sumnum[s]+sumnum[b];
            pre[b]=s;
          }
          if(b==s){
            dis[a]=min(c,dis[a]);
            sumnum[a]=sumnum[s]+sumnum[a];
            pre[a]=s;
          }
      }

     dij();
     cout<<l[d]<<" ";
     print(d);
     cout<<sumnum[d]<<endl;cout<<p[0];

     for(int i=1;i<cn;i++){cout<<" "<<p[i];}cout<<endl;

    return 0;
}