Susu

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(){
for(int i=1;i<=n;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]){
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();
}
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;
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]){
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();
}
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; //小根堆，取距离最小值
}
});
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];
}
}
}
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();
}
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;
}
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();
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;
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();
}
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{
int n = Integer.valueOf(s[0]);
int m = Integer.valueOf(s[1]);
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){