头像

Susu


访客:2047

离线:1个月前



Susu
4个月前
import java.util.*;
class Edge{
    int a;  int b;    int w;
    public Edge(int a,int b,int w){
        this.a=a;   this.b=b;   this.w=w;
    }
}
public class Main {
    static int N = 100010;
    static int n,m;
    static int[] p = new int[N];
    static int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        Edge[] edge = new Edge[m];
        for(int i=0;i<m;i++){
            int a = sc.nextInt();   int b = sc.nextInt();   int w = sc.nextInt();
            Edge e = new Edge(a,b,w);
            edge[i]=e;
        }
        Arrays.sort(edge, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                if(o1.w<o2.w)   return -1;
                else if(o1.w>o2.w)  return 1;
                else return 0;
            }
        });
        for(int i=1;i<n;i++)    p[i]=i;
        int res=0,cnt=0;
        for(int i=0;i<m;i++){
            int a = edge[i].a;  int b = edge[i].b;  int w = edge[i].w;
            a = find(a);b=find(b);
            if(a!=b){
                p[a]=b; res+=w; cnt++;
            }
        }
        if(cnt<n-1) System.out.println("impossible");
        else System.out.println(res);
    }
}






Susu
4个月前
import java.util.*;

public class Main{
    static int N = 510;
    static int n,m;
    static int[][] g = new int[N][N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int prim(){
        for(int i=0;i<N;i++){
            dist[i]=0x3f3f3f3f;
        }
        int res = 0;
        for(int i=0;i<n;i++){
            int t = -1;
            for(int j=1;j<=n;j++){
                if(!st[j] && (t==-1 || dist[t]>dist[j])){
                    t = j;
                }
            }
            if(i>0 && dist[t]==0x3f3f3f3f)    return 0x3f3f3f3f;
            if(i>0) res+=dist[t];
            for(int j=1;j<=n;j++){
                dist[j] = Math.min(dist[j],g[t][j]);
            }
            st[t]=true;
        }
        return res;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                g[i][j]=0x3f3f3f3f;
            }
        }
        while(m-->0){
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            g[x][y] = Math.min(g[x][y], z);
            g[y][x] = Math.min(g[y][x], z);
        }
        int t = prim();
        if(t==0x3f3f3f3f)   System.out.print("impossible");
        else System.out.print(t);
    }
}




Susu
4个月前
import java.util.*;

public class Main{
    static int N = 510;
    static int n,m,k;
    static int[][] dist = new int[N][N];
    static void floyd(){
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    dist[i][j]=Math.min(dist[i][j],dist[i][k]+dist[k][j]);
                }
            }
        }
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(i==j)    dist[i][j]=0;
                else    dist[i][j]=0x3f3f3f;
            }
        }
        while(m-->0){
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            dist[x][y] = Math.min(dist[x][y], z);
        }
        floyd();
        while(k-->0){
            int x = sc.nextInt();
            int y = sc.nextInt();
            if(dist[x][y]>0x3f3f3f/2)    System.out.println("impossible");
            else    System.out.println(dist[x][y]);
        }
    }
}



Susu
4个月前
import java.util.*;

public class Main {
    static int N = 10010;//边数M
    static int n,m;
    static int idx;
    static int[] h = new int[N];
    static int[] w = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] cnt = new int[N];
    static int[] dist = new int[N];      //用于记录每一个点距离第一个点的距离
    static boolean[] st = new boolean[N];//用于记录该点的最短距离是否已经确定
    static boolean spfa(){
        Queue<Integer> q = new LinkedList<>();
        for(int i=1;i<=n;i++){
            q.add(i);
            st[i]=true;
        }
        while(!q.isEmpty()){
           int t = q.poll();
           st[t]=false;
           for(int i=h[t];i!=-1;i=ne[i]){
               int j = e[i];
               if(dist[j]>dist[t]+w[i]){
                   dist[j]=dist[t]+w[i];
                   cnt[j]=cnt[t]+1;
                   if(cnt[j]>=n)    return true;
                   if(!st[j]){
                       q.add(j);
                       st[j]=true;
                   }
               }
           }
        }
        return false;
    }
    static void add(int a,int b,int c){
        e[idx]=b;   w[idx]=c;   ne[idx]=h[a];   h[a]=idx++;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i=0;i<N;i++){
            h[i]=-1;
        }
        while(m-->0){
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            add(x,y,z);
        }
        if(spfa())  System.out.print("Yes");
        else System.out.print("No");
    }
}




Susu
4个月前
import java.util.*;

public class Main {
    static int N = 100010;//边数M
    static int n,m;
    static int idx;
    static int[] h = new int[N];
    static int[] w = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] dist = new int[N];      //用于记录每一个点距离第一个点的距离
    static boolean[] st = new boolean[N];//用于记录该点的最短距离是否已经确定
    static int spfa(){
        for(int i=0;i<N;i++){
            dist[i]=0x3f3f3f;            //初始化距离  0x3f代表无限大
        }
        dist[1]=0;
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        st[1]=true;
        while(!q.isEmpty()){
           int t = q.poll();
           st[t]=false;
           for(int i=h[t];i!=-1;i=ne[i]){
               int j = e[i];
               if(dist[j]>dist[t]+w[i]){
                   dist[j]=dist[t]+w[i];
                   if(!st[j]){
                       q.add(j);
                       st[j]=true;
                   }
               }
           }
        }
        if(dist[n]==0x3f3f3f)   return -1; //如果第n个点路径为无穷大即不存在最低路径
        return dist[n];
    }
    static void add(int a,int b,int c){
        e[idx]=b;   w[idx]=c;   ne[idx]=h[a];   h[a]=idx++;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i=0;i<N;i++){
            h[i]=-1;
        }
        while(m-->0){
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            add(x,y,z);
        }
        if(spfa()==-1)  System.out.print("impossible");
        else System.out.print(spfa());
    }
}




Susu
4个月前
import java.util.*;

class Node{
    int distance;
    int num;
    public Node(int distance,int num){
        this.distance=distance;
        this.num=num;
    }
}
public class Main {
    static int N = 100010;//边数M
    static int n,m;
    static int idx;
    static int[] h = new int[N];
    static int[] w = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] dist = new int[N];      //用于记录每一个点距离第一个点的距离
    static boolean[] st = new boolean[N];//用于记录该点的最短距离是否已经确定
    static int dijkstra(){
        for(int i=0;i<N;i++){
            dist[i]=0x3f3f3f;            //初始化距离  0x3f代表无限大
        }
        dist[1]=0;
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.distance<o2.distance?-1:1; //小根堆,取距离最小值
            }
        });
        pq.add(new Node(0,1));
        while(!pq.isEmpty()){
            Node t = pq.poll();
            int num = t.num;
            int distance = t.distance;
            if(st[num]) continue;
            st[num]=true;
            for(int i=h[num];i!=-1;i=ne[i]){
                int j = e[i];
                if(dist[j]>distance+w[i]){
                    dist[j]=distance+w[i];
                    pq.add(new Node(dist[j],j));
                }
            }
        }
        if(dist[n]==0x3f3f3f)   return -1; //如果第n个点路径为无穷大即不存在最低路径
        return dist[n];
    }
    static void add(int a,int b,int c){
        e[idx]=b;   w[idx]=c;   ne[idx]=h[a];   h[a]=idx++;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i=0;i<N;i++){
            h[i]=-1;
        }
        while(m-->0){
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            add(x,y,z);
        }
        System.out.print(dijkstra());
    }
}




Susu
4个月前
import java.util.*;

public class Main{
    static int N = 510;
    static int n,m;
    static int[][] g = new int[N][N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int dijkstra(){
        for(int i=0;i<N;i++){
            dist[i]=0x3f3f3f;
        }
        dist[1]=0;
        for(int i=0;i<n;i++){
            int t = -1;
            for(int j=1;j<=n;j++){
                if(!st[j] && (t==-1 || dist[t]>dist[j])){
                    t = j;
                }
            }
            st[t] = true;
            for(int j=1;j<=n;j++){
                dist[j] = Math.min(dist[j],dist[t]+g[t][j]);
            }
        }
        if(dist[n]==0x3f3f3f)  return -1;
        return dist[n];
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                g[i][j]=0x3f3f3f;
            }
        }
        while(m-->0){
            int x = sc.nextInt();
            int y = sc.nextInt();
            int z = sc.nextInt();
            g[x][y] = Math.min(g[x][y], z);
        }
        System.out.print(dijkstra());
    }
}



Susu
4个月前
import java.util.*;

public class Main{
    static int N = 100010;
    static int[] h = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int n,m;
    static int idx;
    static int[] q = new int[N];
    static int[] d = new int[N];
    static boolean topSort(){
        int hh=0,tt=-1;
        for(int i=1;i<=n;i++){
            if(d[i]==0){
                q[++tt]=i;
            }
        }
        while(hh<=tt){
            int t = q[hh++];
            for(int i=h[t];i!=-1;i=ne[i]){
                int j = e[i];
                d[j]--;
                if(d[j]==0) q[++tt]=j;
            }
        }
        return tt == n-1;
    }
    static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i=0;i<N;i++){
            h[i]=-1;
        }
        while(m-->0){
            int x = sc.nextInt();
            int y = sc.nextInt();
            add(x,y);
            d[y]++;
        }
        if(topSort()){
            for(int i=0;i<n;i++){
                System.out.print(q[i]+" "); 
            }
        }else{
            System.out.print("-1"); 
        }
    }
}



Susu
4个月前
import java.util.*;

public class Main{
    static int N = 100010;
    static int[] q = new int[N];
    static int[] d = new int[N];
    static int[] e = new int[N];
    static int[] ne = new int[N];
    static int[] h = new int[N];
    static int idx;
    static void add(int a,int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        for(int i=0;i<N;i++){
            h[i]=-1;
        }
        while(m-->0){
            int a = sc.nextInt();
            int b = sc.nextInt();
            add(a,b);
        }
        for(int i=0;i<N;i++){
            d[i]=-1;
        }
        int hh=0,tt=0;
        q[0] = 1;d[1]=0;
        while(hh<=tt){
            int t = q[hh++];
            for(int i=h[t];i!=-1;i=ne[i]){
                int j = e[i];
                if(d[j]==-1){
                    d[j] = d[t]+1;
                    q[++tt] = j;
                }
            }
        }
       System.out.print(d[n]);
    }
}



Susu
4个月前
import java.io.*;

public class Main{
    static int N = 100010;
    static int P = 131;
    static char[] c = new char[N];
    static long[] p = new long[N];
    static long[] h = new long[N];
    static long get(int l,int r){
        return h[r]-h[l-1]*p[r-l+1];
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.valueOf(s[0]);
        int m = Integer.valueOf(s[1]);
        String str = br.readLine();
        p[0] = 1;
        for(int i=1;i<=n;i++){
            c[i] = str.charAt(i-1);
            p[i] = p[i-1]*P;
            h[i] = h[i-1]*P + c[i];
        }
        while(m-->0){
            String[] strs = br.readLine().split(" ");
            int l1 = Integer.valueOf(strs[0]);int r1 = Integer.valueOf(strs[1]);
            int l2 = Integer.valueOf(strs[2]);int r2 = Integer.valueOf(strs[3]);
            if(get(l1,r1)==get(l2,r2))  System.out.println("Yes");
            else    System.out.println("No"); 
        }
    }
}