for k = k * 2: for i in V: for j in V: for u in V: dist[i][j][k] <- min(dist[i][j][k / 2], dist[i][u][k / 2] + dist[u][j][k / 2])
另一种解法
一条最短路径 一定包含0个或者若干个中间点。
如果我们选择点集 中前 个点 作为中间点,那么它有一条很好的性质:
如果 的最短路径中不包含 ,那么
如果 的最短路径中包含 ,那么
所以我们可以写出状态转移方程
举例说明
伪代码
1 2 3 4 5 6 7 8 9 10
Floyd-Warshall(G{V,E}): for i = j: dist[i][j] <- 0 for i != j dist[i][j] <- w[i][j] for k in V: for i in V: for j in V: dist[i][j] <- min(dist[i][j], dist[i][k] + dist[k][j]) pre[i][j] <- pre[k][j] if dist[i][k] + dist[k][j] smaller
printf("Hi there!\b, "); printf("welcame!\b\b\b\bo\n"); printf("Please type your name: ____.\b\b\b\b"); scanf("%s",name); ---------------------------------------- Output: Hi there, welcome! //输入John Please type your name: John.
//Environment: Ubuntu 20.04, gcc, zsh //Not sure about whether this will work on windows. //Windows 10 and windows terminal support ANSI escape sequence //so if you are using them, this should work properly. #include<stdio.h> #include<unistd.h>
intmain(){ printf("Hello, Welcome to this ANSI escape sequence test\n"); printf("\033[33mNow, we are printing in yellow\n"); printf("\033[4mYou can also underline sentences.\n"); printf("\033[0;31mBesides, you can print in red.\n"); printf("\033[0mHopefully, you understand what's happening.\n"); sleep(8); printf("\033[0m\033[2J\033[H"); printf("\033[32mTry to input something,press CTRL-D to end input\n"); while(getchar() != EOF); printf("\nYou see, text you typed in are green."); return0; }
voidPrintProgressBar(int progress, int interval, int theme){ //progress is a number in range [0,100] indicating the progress of a work. //interval is the time waited between each function call. Count in seconds. //theme is the choice of theme in which the progress bar is presented. putchar('\r'); printf("\033[?25l"); staticint in_frame = 0; constint MAXWIDTH = 50; constchar frame[] = {'|','/','-','\\'}; constint FRAMELEN = 4; int width = progress*MAXWIDTH/100; switch (theme){ case1: // \ | / - and number in the end printf("%c %d%%", frame[in_frame],progress); in_frame = (in_frame + 1) % FRAMELEN; break; case2: putchar('['); for(int i = 0; i < width; i++){ putchar('='); } putchar('>'); for(int i = width+1; i <= MAXWIDTH; i++){ putchar(' '); } putchar(']'); printf(" %d%%",progress); default: putchar('['); for(int i = 0; i < width; i++){ putchar('='); } putchar('>'); for(int i = width+1; i <= MAXWIDTH; i++){ putchar(' '); } putchar(']'); printf(" %c %d%%", frame[in_frame],progress); in_frame = (in_frame + 1) % 4; } printf("\033[K"); sleep(interval); //Linux uses line buffer when printing in terminal,which means //that you need to tell the terminal when to end the line //by sending a newline character, printing enough content to fill up the buffer //or getting an input. // //Since we are always on the same line printing short sentences,we satisify 0 of 3 conditions. //There's no way that computer will print the content in buffer. //so we need to use fflush whose function is //telling the computer to print all characters in buffer. fflush(stdout); }
intmain(){ for(int i = 1; i <= 100; i++){ PrintProgressBar(i,1,0); } printf("\033[?25h"); return0; }
跳舞的颜文字
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
#include<stdio.h> #include<stdlib.h> #include<unistd.h> intmain(){ constint syn_size = 2,TIME = 100; char syn[][1000] = {"└|``┌|","|┐``|┘"}; printf("\033[?25l"); for(int T = 0; T < TIME; T++){ for (int i = 0; i < syn_size; i++){ printf("\r%s", syn[i]); fflush(stdout); sleep(1);